1.概念
鍊式存儲結構:是指把資料元素存放在任意記憶體未被占用的存儲單元裡,這組存儲單元可以是連續的,也可以是不連續的。
大概就是這樣:
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLicmbw5CMjJTN0YGNiVGMjVDN1ETYhdTMhhDNxkDO2EzNjZTNi9CX0JXZ252bj91Ztl2Lc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
是以,為了表示每個資料元素a1,與其直接後繼資料元素 a2 之間的邏輯關系,對資料元素a來說,除了存儲其本身的資訊之外,還需存儲一個訓示其直接後繼的資訊(即直接後繼的存儲位置)。
對此有如下幾個概念:
資料域
指針域
指針(鍊)
頭指針
存儲資料元素資訊的域
存儲直接後繼位置的域
指針域中存儲的資訊
指向第一個結點的指針,具有辨別作用常冠以連結清單名字,是連結清單的必要元素
結點
連結清單
單連結清單
頭結點
資料域與指針域的結合
n 個結點按一定邏輯次序的鍊結
連結清單的每個結點中隻包含一個指針域
放在第一進制素結點之前,資料域一般無意義,非必要
下圖即為一個單連結清單:
2.實作
完整代碼下載下傳位址:https://download..net/download/luotuoxiansheng/10756421
(1)建立結點結構
typedef struct SlNode
{
ElemType1 name[DATA1LENGTH]; //建立數組存儲空間
ElemType2 number[DATA2LENGTH];
ElemType2 length; //辨別表長
struct SlNode *next; //建立指向結點的指針
}SlNode,*LinkList;
(2)建立表單
建立結點資料并利用尾插法依次插傳入連結表,形成初始的單連結清單
示例代碼:
void CreateList(SlNode *L)
{
SlNode *p,*newnode;
L->length=0;
p=L;
char flag='y';
puts("建立表單:");
while(flag=='Y'||flag=='y'){
newnode=(LinkList)malloc(sizeof(SlNode));
printf("name:");
scanf("%s",newnode->name);
printf("number:");
scanf("%d",newnode->number);
//節點插入(尾部)
newnode->next=NULL;
p->next=newnode;
p=newnode;
L->length++;
getchar();//等待輸入完成後的Enter鍵
printf("繼續輸入?(y/n)");
scanf("%c",&flag);
}
}
結果示範:
(3)增:在第i個位置插入資料
示例代碼:
void SListInsert(SlNode *L)
{
int i;
int j=1,n=1;
SlNode *p,*newnode;
p=L;
printf("在第幾個位置插入?請輸入:");
scanf("%d",&i);
if (i>(L->length+1)||i
{
printf("error!節點不存在!\n");
return;
}
while (j
{
p=p->next;
j++;
}
//找到插入位置後建立結點資料
newnode=(LinkList)malloc(sizeof(SlNode));
printf("name: ");
scanf("%s",newnode->name);
printf("number: ");
scanf("%d",newnode->number);
//插入
newnode->next=p->next;
p->next=newnode;
if(i==L->length+1)//如果是在尾部插入,則讓newnode->next=NULL;
newnode->next=NULL;
L->length++;
}
結果示範:
可在任意位置插入結點。依次在尾部、頭部、第i個結點處插入:
尾插:
頭插:
第3個結點處:
(4)删:删除第i個資料
示例代碼:
Status SListDelete(SlNode *L)
{
int j=1;
int i;
SlNode *p=L;
SlNode *q;
printf("請輸入Nob:");
scanf("%d",&i);
if (i>(L->length)||i
{
printf("error!節點不存在!\n");
return 0;
}
while (j
{
p=p->next;
j++;
}
//删除q節點
q=p->next;
p->next=q->next;
free(q);
--(L->length);
return 1;
}
結果示範:
删除第三個結點
(5)改:更改資料
示例代碼:
Status SListUpdate(SlNode *L)
{
int j=1;
int i;
SlNode *p=L->next;
printf("請輸入Nob:");
scanf("%d",&i);
if (i>(L->length)||i
{
printf("error!節點不存在!\n");
return 0;
}
while (j
{
p=p->next;
j++;
}
printf("新name:");
scanf("%s",p->name);
printf("新number:");
scanf("%d",p->number);
return 1;
}
結果示範:
更改第三個結點資料
(6)查:查找資料
本例程中若要查找字元串類型的資料,在c語言中應使用strcmp()函數去比對查找,不能直接使用“==”比對,筆者因為這個問題在這出現了很多錯誤。
示例代碼:
SlNode *SListGet(SlNode *L)
{
int n;
ElemType2 Nob;
int ch;
SlNode *p;
SlNode *input;
SlNode *get;
p=L->next;
input=(LinkList)malloc(sizeof(SlNode));//建立結點用于存儲輸入資料
printf("查找項(1.Nob/2.name/3.number):");
scanf("%d",&ch);
switch(ch)
{
case 1:{
printf("請輸入Nob:");
scanf("%d",&Nob);
n=1;
while(n<=L->length)
{
if(Nob==n)
{
get=p;
return get;
}
p=p->next;
n++;
}
printf("沒有此資料!\n");return 0;
};break;
case 2:{
n=1;
printf("請輸入name:");
scanf("%s",input->name);
while(n<=L->length)
{
if(!strcmp(p->name,input->name))//若兩個字元串相等
{
get=p;
return get;//找到就傳回
}
p=p->next;
n++;
}
printf("沒有此資料!\n");return 0;
};break;
case 3:{
n=1;
printf("請輸入number:");
scanf("%d",input->number);
while(n<=L->length)
{
if(*p->number==*input->number)
{
get=p;
return get;//找到就傳回
}
p=p->next;
n++;
}
printf("沒有此資料!\n");return 0;
};break;
default: printf("錯誤!沒有這個選項!\n");
}
}
結果示範:
按序号查找:
按name查找:
按number查找:
(7)排序:對表單按照number升序重新排序(冒泡排序法)
排序方法多種多樣,有兩篇博文對各種排序方法都有不錯的介紹和實作:
https://www..com/eniac12/p/5329396.html#s1
https://www..com/eniac12/p/5332117.html
此處選用冒泡排序,算法示意圖如下:
在單連結清單中使用冒泡排序關鍵在于相鄰兩個結點的交換:
交換後p往後退一格:
示例代碼:
void SListSort(SlNode *L)
{
int i,j;
SlNode *pre=L;
SlNode *p=L->next;
SlNode *tmp;
for (i=0;ilength-1;i++)
{
pre=L;
p=L->next;
for (j=0;jlength-1-i;j++)
{
if (*(p->number)>*(p->next->number))
{
//交換節點
pre->next=p->next;
p->next = p->next->next;
pre->next->next=p;
p=pre->next;//更新p的位置
}
//p再前進一個結點
p=p->next;
pre=pre->next;
}
}
PrintList(L);//列印表單
}
結果示範:
(8)其他
表單列印和清空整表的内容不再詳細寫出,詳見完整代碼,下載下傳位址:https://download..net/download/luotuoxiansheng/10756421
3.優劣勢分析
比較順序表,單連結清單更加靈活,且存儲空間大小不确定。若需要頻繁插入和删除時适合使用單連結清單,以及當線性表中的元素個數變化較大或者根本不知道有多大時宜采用單連結清單結構。
以上就是對單連結清單的學習和分享