数据结构-链表-电话本

实验目的：通过电话本实验加深对链表的理解，学习头插法、尾插法。

实验原理：在单链表中实现“插入”和“删除”操作。假设我们要在线性表的两个数据元素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;
		}
	}
 
}