這篇接著上一篇寫，寫完第二章的四五節。

第2章 棧、隊列、鏈表

• • 第四節 鏈表
  • 第五節 模擬鏈表

第四節 鏈表

首先先介紹一下指針

int a; int *p;//定義了一個整形指針變量p。 p=&a;//將a的地址賦值給指針p

&：取地址符
*：聲明一個指針變量/取指針所指向的內存中的值 malloc：從內存中申請分配指定字節大小的內存空間。 注意：malloc函數的返回類型是void*類型，表示未確定類型的指針。

鏈表中的每一個節點都由兩部分組成，一個具體的數值和下一個節點的地址。

struct node {int data;struct node *next; }

因為下一個節點的類型也是struct node，所以這個指針的類型也必須是struct node*類型的指針。

#include <stdio.h> #include <stdlib.h> //這里創建一個結構體用來表示鏈表的結點類型 struct node { int data; struct node *next; //頭指針初始為空 }; int main() { struct node *head,*p,*q,*t; int i,n,a; scanf("%d",&n); head = NULL;//頭指針初始為空for(i=1;i<=n;i++)//循環讀入n個數{ scanf("%d",&a); //動態申請一個空間，用來存放一個結點，并用臨時指針p指向這個結點p=(struct node *)malloc(sizeof(struct node)); p->data=a;//將數據存儲到當前結點的data域中p->next=NULL;//設置當前結點的后繼指針指向空，也就是當前結點的下一個結點為空if(head==NULL) head=p;//如果這是第一個創建的結點，則將頭指針指向 這個結點else q->next=p;//如果不是第一個創建的結點，則將上一個結點的后繼指針指向當前結點q=p;//指針q也指向當前結點}//輸出鏈表中的所有數t=head; while(t!=NULL) { printf("%d ",t->data); t=t->next;//繼續下一個結點}getchar();getchar(); return 0; }

如果要插入一個數，可將代碼改為：

#include <stdio.h> #include <stdlib.h> //這里創建一個結構體用來表示鏈表的結點類型 struct node { int data; struct node *next; };int main() { struct node *head,*p,*q,*t; int i,n,a; scanf("%d",&n); head = NULL;//頭指針初始為空for(i=1;i<=n;i++)//循環讀入n個數{ scanf("%d",&a); //動態申請一個空間，用來存放一個結點，并用臨時指針p指向這個結點p=(struct node *)malloc(sizeof(struct node)); p->data=a;//將數據存儲到當前結點的data域中p->next=NULL;//設置當前結點的后繼指針指向空，也就是當前結點的下一個結點為空if(head==NULL) head=p;//如果這是第一個創建的結點，則將頭指針指向這個結點else q->next=p;//如果不是第一個創建的結點，則將上一個結點的后繼指針指向當前結點q=p;//指針q也指向當前結點} scanf("%d",&a);//讀入待插入的數t=head;//從鏈表頭部開始遍歷while(t!=NULL)//當沒有到達鏈表尾部的時候循環{ if(t->next->data > a)//如果當前結點下一個結點的值大于待插入數，將數插入到中間{ p=(struct node *)malloc(sizeof(struct node));//動態申請一個空間，用來存放新增結點p->data=a; p->next=t->next;//新增結點的后繼指針指向當前結點的后繼指針所指向的結點t->next=p;//當前結點的后繼指針指向新增結點break;//插入完畢退出循環} t=t->next;//繼續下一個結點} //輸出鏈表中的所有數t=head; while(t!=NULL) { printf("%d ",t->data); t=t->next;//繼續下一個結點} getchar();getchar(); return 0; }

第五節 模擬鏈表

第一個整型數組 data 是用來存放序列中具體數字的，另外一個整型
數組 right 是用來存放當前序列中每一個元素右邊的元素在數組 data 中位置的。
想要把6插入到5和8之間，只需要把6放到data[10]，然后right[3]改為10，表示新序列中3號元素右邊的元素存放在data[10]中。再將right[10]改為 4，表示新序列中 10 號元素右邊的元素存放在 data[4]中。

完整的代碼：

#include <stdio.h> int main() { int data[101],right[101]; int i,n,t,len; //讀入已有的數 scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&data[i]); len=n; //初始化數組right for(i=1;i<=n;i++) { if(i!=n) right[i]=i+1; else right[i]=0; } //直接在數組data的末尾增加一個數 len++; scanf("%d",&data[len]); //從鏈表的頭部開始遍歷 t=1; while(t!=0) { if(data[right[t]]>data[len])//如果當前結點下一個結點的值大于待插入數，將數插入到中間 { right[len]=right[t];//新插入數的下一個結點標號等于當前結點的下一個結點編號 right[t]=len;//當前結點的下一個結點編號就是新插入數的編號 break;//插入完成跳出循環 } t=right[t]; } //輸出鏈表中所有的數 t=1; while(t!=0) { printf("%d ",data[t]); t=right[t]; } getchar(); getchar(); return 0; }

模擬鏈表采用一個一維數組來儲存數據數組的索引號，來達到存儲指針地址的效果，但是相比之下更簡潔方便。
謝謝你的堅持閱讀ovo喲，讓我們一起加油吖

總結

以上是生活随笔為你收集整理的《啊哈！算法》笔记_Day03的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。