1.線性表——鏈表結構與順序存儲結構優(yōu)缺點對比
存儲分配方式：
? 順序存儲結構???段連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素
? 單鏈表采?鏈式存儲結構,??組任意的存儲單元存放線性表的元素
時間性能:
? 查找
? 順序存儲 O(1)
? 單鏈表O(n)
? 插?和刪除
? 存儲結構需要平均移動?個表??半的元素,時間O(n)
? 單鏈表查找某位置后的指針后,插?和刪除為 O(1)
空間性能:
? 順序存儲結構需要預先分配存儲空間,分太?,浪費空間;分?了,發(fā)?上溢出
? 單鏈表不需要分配存儲空間,只要有就可以分配, 元素個數(shù)也不受限制
2.線性表——循環(huán)鏈表
image
2.1 循環(huán)鏈表的初始化及賦值
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 20 /* 存儲空間初始分配量 */
typedef int Status;/* Status是函數(shù)的類型,其值是函數(shù)結果狀態(tài)代碼涩馆，如OK等 */
typedef int ElemType;/* ElemType類型根據(jù)實際情況而定彭则，這里假設為int */
//定義結點
typedef struct Node{
ElemType data;
struct Node *next;
}Node;
typedef struct Node * LinkList;
2種情況:① 第一次開始創(chuàng)建; ②已經(jīng)創(chuàng)建,往里面新增數(shù)據(jù)
判斷是否第一次創(chuàng)建鏈表
YES->創(chuàng)建一個新結點,并使得新結點的next 指向自身; (*L)->next = (*L);
NO-> 找鏈表尾結點,將尾結點的next = 新結點. 新結點的next = (*L);
Status CreateList(LinkList *L){
int item;
LinkList temp = NULL;
LinkList target = NULL;
printf("輸入節(jié)點的值，輸入0結束\n");
while(1)
{
scanf("%d",&item);
if(item==0) break;
//如果輸入的鏈表是空仔夺。則創(chuàng)建一個新的節(jié)點，使其next指針指向自己 (*head)->next=*head;
if(*L==NULL)
{
*L = (LinkList)malloc(sizeof(Node));
if(!L)exit(0);
(*L)->data=item;
(*L)->next=*L;
}
else
{
//輸入的鏈表不是空的激蹲，尋找鏈表的尾節(jié)點扫沼，使尾節(jié)點的next=新節(jié)點。新節(jié)點的next指向頭節(jié)點
for (target = *L; target->next != *L; target = target->next);
temp=(LinkList)malloc(sizeof(Node));
if(!temp) return ERROR;
temp->data=item;
temp->next=*L; //新節(jié)點指向頭節(jié)點
target->next=temp;//尾節(jié)點指向新節(jié)點
}
}
return OK;
}
優(yōu)化方案：設置一個指針r 指向最后一個節(jié)點
Status CreateList2(LinkList *L){
int item;
LinkList temp = NULL;
LinkList r = NULL;
printf("請輸入新的結點, 當輸入0時結束!\n");
while (1) {
scanf("%d",&item);
if (item == 0) {
break;
}
//第一次創(chuàng)建
if(*L == NULL){
*L = (LinkList)malloc(sizeof(Node));
if(!*L) return ERROR;
(*L)->data = item;
(*L)->next = *L;
r = *L;
}else{
temp = (LinkList)malloc(sizeof(Node));
if(!temp) return ERROR;
temp->data = item;
temp->next = *L;
r->next = temp;
r = temp;
}
}
return OK;
}
2.2 遍歷循環(huán)鏈表
循環(huán)鏈表的遍歷最好用do while語句缤剧，因為頭節(jié)點就有值
void show(LinkList p) {
//如果鏈表是空
if(p == NULL){
printf("打印的鏈表為空!\n");
return;
}else{
LinkList temp;
temp = p;
do{
printf("%5d",temp->data);
temp = temp->next;
}while (temp != p);
printf("\n");
}
}
2.3 循環(huán)鏈表插入數(shù)據(jù)
image
image
Status ListInsert(LinkList *L, int place, int num){
LinkList temp ,target;
int i;
if (place == 1) {
//如果插入的位置為1,則屬于插入首元結點,所以需要特殊處理
//創(chuàng)建新結點temp,并判斷是否創(chuàng)建成功,成功則賦值,否則返回ERROR;
temp = (LinkList)malloc(sizeof(Node));
if (temp == NULL) {
return ERROR;
}
temp->data = num;
//找到鏈表最后的結點_尾結點
for (target = *L; target->next != *L; target = target->next);
//讓新結點的next 執(zhí)行頭結點
temp->next = *L;
//尾結點的next 指向新的頭結點
target->next = temp;
//讓頭指針指向temp(臨時的新結點)
*L = temp;
} else {
//如果插入的位置在其他位置;
//創(chuàng)建新結點temp,并判斷是否創(chuàng)建成功,成功則賦值,否則返回ERROR;
temp = (LinkList)malloc(sizeof(Node));
if (temp == NULL) {
return ERROR;
}
temp->data = num;
//先找到插入的位置,如果超過鏈表長度,則自動插入隊尾;
for ( i = 1,target = *L; target->next != *L && i != place - 1; target = target->next,i++);
//通過target找到要插入位置的前一個結點, 讓target->next = temp
temp->next = target->next;
//插入結點的前驅(qū)指向新結點,新結點的next 指向target原來的next位置
target->next = temp;
}
return OK;
}
2.4 循環(huán)鏈表刪除數(shù)據(jù)
Status LinkListDelete(LinkList *L,int place){
LinkList temp,target;
int i;
//temp 指向鏈表首元結點
temp = *L;
if(temp == NULL) return ERROR;
if (place == 1) {
//如果刪除到只剩下首元結點了,則直接將*L置空;
if((*L)->next == (*L)){
(*L) = NULL;
return OK;
}
//鏈表還有很多數(shù)據(jù),但是刪除的是首結點;
//1. 找到尾結點, 使得尾結點next 指向頭結點的下一個結點 target->next = (*L)->next;
//2. 新結點做為頭結點,則釋放原來的頭結點
for (target = *L; target->next != *L; target = target->next);
temp = *L;
*L = (*L)->next;
target->next = *L;
free(temp);
} else {
//如果刪除其他結點--其他結點
//1. 找到刪除結點前一個結點target
//2. 使得target->next 指向下一個結點
//3. 釋放需要刪除的結點temp
for(i=1,target = *L;target->next != *L && i != place -1;target = target->next,i++) ;
temp = target->next;
target->next = temp->next;
free(temp);
}
return OK;
}
2.5 循環(huán)鏈表查詢值
int findValue(LinkList L,int value) {
int i = 1;
LinkList p;
p = L;
//尋找鏈表中的結點 data == value
while (p->data != value && p->next != L) {
i++;
p = p->next;
}
//當尾結點指向頭結點就會直接跳出循環(huán),所以要額外增加一次判斷尾結點的data == value;
if (p->next == L && p->data != value) {
return -1;
}
return i;
}
