資料結構-連結清單-電話本

實驗目的：通過電話本實驗加深對連結清單的了解，學習頭插法、尾插法。

實驗原理：在單連結清單中實作“插入”和“删除”操作。假設我們要線上性表的兩個資料元素A和B之間插入一個資料元素X，已知P為其單連結清單存儲結構中指向結點A的指針。

為插入資料元素X，首先要生成一個資料域為X的結點，然後插入在單連結清單中。根據插入操作的邏輯定義，還需要修改結點A中的指針域，令其指向結點X，而結點X中的指針域應指向結點B，進而實作3個元素A、B和X之間邏輯關系的變化。假設S為指向結點X的指針：

• s->next=p->next;p->next=s

反之，删除元素B時，隻需修改結點A中的指針域。假設P為指向結點A的指針，則修改指針的文法為

• p->next=p->next->next

2、材料與方法

連結清單：

連結清單是一種常見的重要的資料結構。它是動态地進行存儲配置設定的一種結構。它可以根據需要開辟記憶體單元。連結清單有一個“頭指針”變量，以head表示，它存放一個位址。該位址指向一個元素。連結清單中每一個元素稱為“結點”，每個結點都應包括兩個部分：一為使用者需要用的實際資料，二為下一個結點的位址。是以，head指向第一個元素：第一個元素又指向第二個元素；……，直到最後一個元素，該元素不再指向其它元素，它稱為“表尾”，它的位址部分放一個“NULL”（表示“空位址”），連結清單到此結束。

方法：頭插法或尾插法。

頭插法：

void HeadCreatList(List *L) //頭插法建立連結清單

{

List s; //不用像尾插法一樣生成一個終端節點。

L->next = NULL;

for (int i = 0; i < 10; i++) {

s = (struct List) malloc(sizeof(struct List));//s指向新申請的節點

s->data = i;//用新節點的資料域來接受i

s->next = L->next; //将L指向的位址指派給S;//頭插法與尾插法的不同之處主要在此，

//s所指的新節點的指針域next指向L中的開始節點

L->next = s; //頭指針的指針域next指向s節點，使得s成為開始節點。

}

}

尾插法：

void TailCreatList(List *L) //尾插法建立連結清單

{

List *s, r;//s用來指向新生成的節點。r始終指向L的終端節點。

r = L; //r指向了頭節點，此時的頭節點是終端節點。

for (int i = 0; i < 10; i++) {

s = (struct List) malloc(sizeof(struct List));//s指向新申請的節點

s->data = i; //用新節點的資料域來接受i

r->next = s; //用r來接納新節點

r = s; //r指向終端節點

}

r->next = NULL; //元素已經全部裝傳入連結表L中

//L的終端節點指針域為NULL，L建立完成

}

實驗代碼：

#include<stdio.h>
#include<stdlib.h>

typedef struct Linklist{
	char name[10];
	char number[10];
	struct Linklist *next;
}Linklist,*LNode;

void CreateList_L(Linklist *L){
	Linklist *p,*s;
	p=L;
	puts("建立電話本：");
		s=(LNode)malloc(sizeof(Linklist));
		printf("輸入個人姓名：");
		scanf("%s",s->name);
		printf("輸入個人号碼：");
		scanf("%s",s->number);
		s->next = p->next;
		p->next = s;
		getchar();
	}

void Outprint_L(Linklist *L){
	Linklist *p;
	p=L->next;
	puts("位置\t姓名\t号碼");
	int count=1;
	while(p){
		printf("%d\t%s\t%s\n",count,p->name,p->number);
		p=p->next;
		count++;
	}
}

void Insert_L(Linklist *L){
	Linklist *p,*s;
	p=L;
	int j = 0;
	int i;
	puts("插入位置？");
	scanf("%d",&i);
	while(p && j<i-1){
		p = p->next;
		++j;
	}
	if(!p || j> i-1)
	{	printf("ERROR"); return;}
	s=(LNode)malloc(sizeof(Linklist));
	printf("姓名：");
	scanf("%s",s->name);
	printf("号碼：");
	scanf("%s",s->number);

	s->next=p->next;
	p->next=s;
}

void Delect_L(Linklist *L){
	Linklist *p,*q;
	p=L;
	int n;
	int j = 0;
	puts("删除位置？");
	scanf("%d",&n);
	while(p->next && j<n-1){
		p = p->next;
		++j;
	}
	if(!(p->next)||j>n-1){
		printf("ERROR");
		return;
	}
	q=p->next;
	p->next=q->next;
	free(q);
}
void main(){
	Linklist *L;
	int i;
	L=(LNode)malloc(sizeof(Linklist));
	L->next=NULL;
	CreateList_L(L);
	while(i!=0){
		puts("1.輸出電話号碼\t2.删除\t3.插入\t0.退出");
		scanf("%d",&i);
		switch(i){
		case 1:
			Outprint_L(L);
			break;
		case 2:
			Delect_L(L);
			break;
		case 3:
			Insert_L(L);
			break;
		}
	}
 
}