線性表的鏈式存盤結構

1.相比于線性表的順序存盤結構的優缺點

相比于線性表的順序存盤結構的優點

（1）鏈式存盤時，相鄰資料元素可隨意存放，但所占存盤空間分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指標

優點：插入或洗掉元素時很方便，使用靈活，存盤空間利用率高，

缺點：存盤密度小（<1），查找和修改需要遍歷整個鏈表，

（2）順序存盤時，相鄰資料元素的存放地址也相鄰（邏輯與物理統一）；要求記憶體中可用存盤單元的地址必須是連續的，

優點：存盤密度大（＝1），易于查找和修改，

缺點：插入或洗掉元素時不方便；存盤空間利用率低，預先分配記憶體可能造成存盤空間浪費，

2.線性表的單鏈表儲存結構

//線性表的單鏈表儲存結構
typedef struct node
{
	Elemtype date;
	
	struct node *next;
 } node;
 typedef struct node *list;

3.單鏈表的整表創建 (尾插法)

//單鏈表的整表創建 (尾插法)
void creatlist(list*L,int a[],int n)
{
	list p,r;//r指向鏈表的尾結點， 
	
	int i;
	*L=(list)malloc(sizeof(node));//L為線性表 
	
	r=*L;//定義r指向尾部的結點 
	
	for(i=0;i<n;i++)
	{
		p=(list)malloc(sizeof(node));//生成新結點 
		
		p->date=a[i];
		
		r->next=p;//表尾終端結點的指標指向新節點，就是將將新生成的節點p插入鏈表尾部 
		
		r=p;//r重新指向尾結點 
	}
	r->next=NULL;
 } 

4.單鏈表的整表輸出

void showlist(list L,int n)
 {
 	list p=L->next;
 	while(p)
 	{
 		printf("%3d",p->date);
 		p=p->next;
	 }
	 printf("\n");
  } 

3.單鏈表元素的獲取

int getElem(list L,int i,Elemtype *x)
 {
 	int j=1;//從鏈表第一個結點開始一一檢索 
 	
	list p;//定義一個頭指標 
	
 	p=L->next;
	 	
	for(j=1;j<i;j++)
 	{
 		p=p->next;
	 }
	  if(p==NULL||j>i)//判斷指標p和j是否合法 ，若不合法回傳0 
	 
	 	return 0;
	*x=p->date;//將第i個元素的資料賦給*e； 
	
	return 1;//獲取成功回傳1 
  } 

4.單鏈表的插入

//在原鏈表第i個元素之前插入資料元素X，L的長度++

//單鏈表的插入,在原鏈表第i個元素之前插入資料元素X，L的長度++ 
 int listinsert(list*L,int i,Elemtype x) 
 {
 	int j=1;
	list p=*L;
	list s;//定義一個空結點s；
	for(j=1;j<i;j++)
	{
		p=p->next;
	 } 
	 if(p==NULL||j>i)//判斷指標p和j是否合法 ，若不合法回傳0 
		return 0;
	 s=(list)malloc(sizeof(node));//生成新節點 
	 s->date=x;
	 s->next=p->next;//順序不可改變，若更換就會造成s->next=s; 
	 p->next=s;
	 return 1;
 }

5.//單鏈表的洗掉

//單鏈表的洗掉
 int listdelete(list L,int i,Elemtype*x) 
 {
 	int j=1;
 	list q;
 	list p=L->next;
 	for(j=1;j<i;j++)//遍歷尋找第i個元素 
 	{
 		p=p->next;
	 }
	 if(p->next==NULL||j>i) //若第i個元素不存在，回傳零 
 		return 0;
	 q=p->next;//借用q洗掉第i個結點 
	 p->next=q->next;
	 free(q);//回收洗掉的結點 
	 return 1;
} 

完整代碼詳解

#include<stdio.h>

#include<stdlib.h>

#include<typeinfo> 

typedef int Elemtype;
//線性表的單鏈表儲存結構
typedef struct node
{
	Elemtype date;
	
	struct node *next;
 } node;
 typedef struct node *list;
 
 //單鏈表的整表創建 (尾插法) 
 void creatlist(list*L,int a[],int n)
{
	list p,r;//r指向鏈表的尾結點， 
	
	int i;
	*L=(list)malloc(sizeof(node));//L為線性表 
	
	r=*L;//定義r指向尾部的結點 
	
	for(i=0;i<n;i++)
	{
		p=(list)malloc(sizeof(node));//生成新結點 
		
		p->date=a[i];
		
		r->next=p;//表尾終端結點的指標指向新節點，就是將將新生成的節點p插入鏈表尾部 
		
		r=p;//r重新指向尾結點 
	}
	r->next=NULL;
 } 
 //單鏈表的整表輸出
void showlist(list L,int n)
 {
 	list p=L->next;
 	while(p)
 	{
 		printf("%3d",p->date);
 		p=p->next;
	 }
	 printf("\n");
  } 
 //單鏈表元素的獲取
 int getElem(list L,int i,Elemtype *x)
 {
 	int j=1;//從鏈表第一個結點開始一一檢索 
 	
	list p;//定義一個頭指標 
	
 	p=L->next;
	 	
	for(j=1;j<i;j++)
 	{
 		p=p->next;
	 }
	  if(p==NULL||j>i)//判斷指標p和j是否合法 ，若不合法回傳0 
	 
	 	return 0;
	*x=p->date;//將第i個元素的資料賦給*x； 
	
	return 1;//獲取成功回傳1 
  } 
 //單鏈表的插入,在原鏈表第i個元素之前插入資料元素X，L的長度++ 
 int listinsert(list*L,int i,Elemtype x) 
 {
 	int j=1;
 	
	list p=*L;
	
	list s;//定義一個空結點s；
	
	for(j=1;j<i;j++)
	{
		p=p->next;
	 } 
	 if(p==NULL||j>i)//判斷指標p和j是否合法 ，若不合法回傳0 
	 
		return 0;
		
	 s=(list)malloc(sizeof(node));//生成新節點 
	 
	 s->date=x;
	 
	 s->next=p->next;//順序不可改變，若更換就會造成s->next=s; 
	 
	 p->next=s;
	 
	 return 1;
 }
 //單鏈表的洗掉
 int listdelete(list L,int i,Elemtype *x) 
 {
 	int j=1;
 	
 	list q;
 	
 	list p=L->next;
 	
 	for(j=1;j<i;j++)//遍歷尋找第i個元素 
 	{
 		p=p->next;
	 }
	 if(p->next==NULL||j>i) //若第i個元素不存在，回傳零 
	 
 		return 0;
 		
	 q=p->next;//借用q洗掉第i個結點 
	 
	 p->next=q->next;
	 
	 free(q);//回收洗掉的結點 
	 
	 return 1;
} 

int main()
{
	list L;
	
	int n=5;
	
	printf("請輸入鏈表長度\n");
	
	scanf("%d",&n);
	
	int x,i;
	
	int a[100];
	
	printf("請輸入%d位鏈表的值\n",n);
	
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	creatlist(&L,a,n);
	
	printf("請輸入你要查詢的鏈表中的第i個值\n"); 
	
	scanf("%d",&i);
	
	getElem(L,i,&x);
	
	printf("第%d個值為%d\n",i,x);
	
	printf("請輸入要插入節點的位置z和插入的值x0\n");
	
	int z,x0;
	
	scanf("%d %d",&z,&x0); 
	
	listinsert(&L,z,x0);
	
	printf("此時鏈表的各元素如下\n"); 
	
	showlist( L, n);
	
	printf("請輸入要洗掉的位置o\n"); 
	
	int o;
	
	scanf("%d",&o);
	 
	listdelete( L,o,&x);
	
	showlist( L, n);
 } 

運行結果
注：我本人是在vs上撰寫代碼的，上傳代碼將所有scanf_s改為了scanf；
以便使用其他編譯器運行