线性表，顺序表和链表的区别

存储类别 顺序存储结构 单链表
存储分配方式 用一段连续的存储单元依次存储线性表的数据元素 采用链式存储结构，用一组任意的存储单元存放线性表的元素
时间性能 查找O（1）、插入和删除O（n） 查找O（n）、插入和删除O（1）
空间性能 需要预分配存储空间，分大了浪费，小了容易发生上溢 不需要分配存储空间，只要有就可以分配，元素个数不受限制

通过上面的对比，可以得出一些经验性的结论：

  • 若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。
  • 当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样可以不需要考虑存储空间的大小问题。而如果事先知道线性表的大致长度，用顺序存储结构效率会高很多。

关系图

关系图

基本操作

顺序表

顺序表元素的插入

将代插入的元素插入到线性表的任意位置，那么只需要找到该位置，将其后的元素依次向后移动最后将该位置腾出(从最后一位元素开始)，即可进行填入。

顺序表插入.gif

顺序表元素的删除

找到要删除的元素记录下其位置将准备删除的第i个及其后面的元素依次往前移动即可

顺序表的删除.gif

链表

链表元素的插入

先动态申请空间申请一个新结点r，将数据元素填入r中之后遍历链表找到要插入的位置的前一个位置记作p，让r指向p的下一个元素之后将p指向r，完成插入。

链表插入.gif

链表元素的删除

找到待删除元素的前一个位置记为p，借助新结点r，使r指向p所指的下一个元素,再让p指向r的next，最后释放r；

链表删除.gif

实例代码

顺序表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
//利用顺序表完成一个班级学生课程成绩的简单管理
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define  MAXSIZE  100 //根据需要自己设定一个班级能够容纳的最大学生数
typedef struct stu
{  
	int num;  		  //学生学号
    char name[10];    //学生姓名
    float score;  	  //学生成绩
}STUDENT; 			  //存放单个学生信息的结构体类型

typedef struct list
{
	STUDENT stu[MAXSIZE];  //存放学生的数组定义，静态分配空间
	int length;			   //记录班级实际学生个数
}LIST;					   //存放班级学生信息的顺序表类型

void listcreate(LIST *Li,int m) 
	//初始化班级的学生信息	
    //m为该班级的初始人数
{
  int i;
  Li->length=0;
	for(i=1;i<=m;i++) //输入m个学生的所有信息
	{
		printf("请输入第%d个学生的信息:\n",i);
		printf("学号=");
		scanf("%d",&Li->stu[i].num); //输入第i个学生的学号
		printf("姓名=");
		scanf("%s",&Li->stu[i].name); //输入第i个学生的姓名
		printf("成绩=");
		scanf("%f",&Li->stu[i].score); //输入第i个学生的成绩
		Li->length++; //学生人数加1
 	}
} 

int listinsert(LIST *Li,int i)
		      //将学生插入到班级Li的第i个位置。
			  //插入一个学生信息
{
	int j;
	STUDENT e;

	if(Li->length>=MAXSIZE-1)
		    //测试存储空间是否被占满
	{
		printf("无更多的存储空间!\n");
		return 0;
	}

	if (i<=0||i>=Li->length+2) 
		    //插入位置检验，如果错误就返回0退出程序。
	{
			printf("插入位置有误!\n");
			return 0;	
	}
	else
	{
	  
		printf("请输入插入的学生信息:\n");
		printf("学号=");
			scanf("%d",&e.num); 
		printf("姓名=");
			scanf("%s",e.name); 
		printf("成绩=");
			scanf("%f",&e.score);		
		 for(j=Li->length;j>=i-1;j--)
		 {
		 	Li->stu[j+1]=Li->stu[j];
			 	
		 }                              				                   
		  Li->stu[i]=e;
		  Li->length++;                            ; //利用for循环将第i个及其后面的元素依次往后移动
		                              ; //移开位置后将学生e放入到i位置
		                              ; //完成插入后，学生实际人数加1
		return 1;
   }
}

int listdel(LIST *Li,int i)	
            //删除一个学生信息
			//删除第i个学生的信息
{ 
	int j;
	if (i<=0||i>Li->length)//删除位置检验，如果错误就返回0退出程序。
		return 0;						
	else
	
	{
		 for(j=i;j<=Li->length;j++)
		 {
		 	Li->stu[j]=Li->stu[j+1];
		 }                              
		 Li->length--;                   ; //利用for循环将准备删除的第i个及其后面的元素依次往前移动
		                    ; //删除第i个学生后，学生人数减1
		return 1;
    }
}

void listdisplay(LIST L)
{         //显示所有学生信息
	int i;	
	//printf("班级学生信息如下:\n");
	printf("      学号      姓名      成绩\n");
	for(i=1;i<=L.length;i++)
	printf("%10d%10s%10.2f\n",L.stu[i].num,L.stu[i].name,L.stu[i].score);
}

void showmenu()
{          //显示菜单
	printf("    欢迎使用成绩管理小软件\n");
	printf("\t1、创建学生信息\n");
	printf("\t2、插入学生信息\n");
	printf("\t3、删除学生信息\n");
	printf("\t4、显示学生信息\n");
	printf("\t5、退出程序\n");	
}

void main()
{
	int no,stu_count,pos;
	LIST stu_info;
	while(1)
	{
		showmenu();
		printf("    请输入你的选择：");
		scanf("%d",&no);
		switch(no)
		{
		    case 1:	printf("班级信息初始化,按任意键继续……\n");
	                getch();
	                printf("请输入班级学生原始人数：");
	                scanf("%d",&stu_count);
	                listcreate(&stu_info,stu_count);
					system("cls");
					showmenu();
	                listdisplay(stu_info);
				    printf("班级信息初始化已经完成，按任意键继续……\n");
					getch();
	                system("cls");
					break;
			case 2:printf("插入前班级信息：\n");
				   listdisplay(stu_info);
				   printf("请输入插入位置：");
				   scanf("%d",&pos);				  
				   listinsert(&stu_info,pos);
				   printf("插入后班级信息：\n");
				   listdisplay(stu_info);
				   printf("插入已经完成，按任意键继续……\n");
				   getch();
				   system("cls");
				   break;
			case 3:printf("删除前班级信息：\n");
				   listdisplay(stu_info);
				   printf("请输入删除位置：");
				   scanf("%d",&pos);
				   listdel(&stu_info,pos);
				   printf("删除后班级信息：\n");
				   listdisplay(stu_info);
				   printf("删除已经完成，按任意键继续……\n");
				   getch();
				   system("cls");
				   break;
			case 4:listdisplay(stu_info);
				   printf("显示结果如上所示，按任意键继续……\n");
				   getch();
				   system("cls");
				   break;
			case 5:return;
		}
	}
}

链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#define NULL 0
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct stu
{  
         int num;  				//学生的学号
         char name[10];//学生的姓名
         float score;  		    //学生的成绩
 }STUDENT; 				        //存放单个学生信息的结构体类型

typedef struct node
   { 
      STUDENT  data;       //结点的值
	struct node  *next;  //指向下一个结点的地址
   }SNODE;

void showmenu()
{          //显示菜单
	printf("    欢迎使用成绩管理小软件\n");
	printf("\t1、创建学生信息\n");
	printf("\t2、插入学生信息\n");
	printf("\t3、删除学生信息\n");
	printf("\t4、显示学生信息\n");
	printf("\t5、退出程序\n");	
}

SNODE *listcreate(SNODE *head,int n)		//n为该班级的实际人数
{                                         //建立班级学生信息
	int i; 
	SNODE *p=NULL,*q=NULL;
	p=head;
	for(i=1;i<=n;i++)		//循环插入n个学生
	{
		printf("\n请输入第%d位学生的信息:\n",i);
		q=(SNODE *)malloc(sizeof(SNODE));
		printf("学号=");scanf("%d",&q->data.num);		
		printf("姓名=");scanf("%s",q->data.name);		
		printf("成绩=");scanf("%f",&q->data.score);	
		q->next=NULL;
		p->next=q;
		p=q;
		head->data.num++;
	}
	return head;
}

SNODE *listinsert(SNODE  *head,int i)			//将学生插入到班级Li_head的第i个位置。
{
	SNODE *p,*r;
	int cnt=0;
	p=(SNODE*)malloc(sizeof(SNODE));
	p->next=NULL;
	printf("\n请输入插入学生的信息:\n",i);
	printf("学号=");scanf("%d",&p->data.num);		
	printf("姓名=");scanf("%s",p->data.name);		
	printf("成绩=");scanf("%f",&p->data.score);
	r=head;
	while(r!=NULL&&cnt!=i-1)
	{
		r=r->next;
		cnt++;
	}
	p->next=r->next;
	r->next=p; 
	return head;
}
SNODE *listdel(SNODE *head,int i)	
			//删除链表Li_head中第i个学生的信息
{	
	SNODE *p,*r,*q;
	int cnt=0;
	r=head;
	while(r!=NULL&&cnt!=i-1)
	{
		r=r->next;
		cnt++;
	}
	p=r->next;
	r->next=p->next;
	free(p);
	return head;
}

void listdisplay(SNODE *head)
{
     //显示所有学生信息
	SNODE *p;
	p=head->next;
	printf("班级学生信息如下:\n");
	printf("      学号      姓名      成绩\n");
	while(p!=NULL)
	 	{
         printf("%10d%10s%10.2f\n",p->data.num,p->data.name,p->data.score);
		 p=p->next;
		}
}

void main()      
{
	SNODE *head=NULL;
	int no,stu_count,pos;
head=(SNODE *)malloc(sizeof(SNODE));//动态建立第一个结点，作为头结点，head指针指向它，
head->data.num=0;                  //链表为带头结点的单链表
	head->next=NULL;
	while(1)
	{
		showmenu();
		printf("    请输入你的选择：");
		scanf("%d",&no);
		switch(no)
		{
		    case 1:	printf("班级信息初始化,按任意键继续……\n");
	                getch();
	                printf("请输入班级学生原始人数：");
	                scanf("%d",&stu_count);
	                head=listcreate(head,stu_count);
					system("cls");
					showmenu();
	                listdisplay(head);
				    printf("班级信息初始化已经完成，按任意键继续……\n");
					getch();
	                system("cls");
					break;
			case 2:printf("插入前班级信息：\n");
				   listdisplay(head);
				   printf("请输入插入位置：");
				   scanf("%d",&pos);				  
				   head=listinsert(head,pos);
				   printf("插入后班级信息：\n");
				   listdisplay(head);
				   printf("插入已经完成，按任意键继续……\n");
				   getch();
				   system("cls");
				   break;
			case 3:printf("删除前班级信息：\n");
				   listdisplay(head);
				   printf("请输入删除位置：");
				   scanf("%d",&pos);
				   head=listdel(head,pos);
				   printf("删除后班级信息：\n");
				   listdisplay(head);
				   printf("删除已经完成，按任意键继续……\n");
				   getch();
				   system("cls");
				   break;
			case 4:listdisplay(head);
				   printf("显示结果如上所示，按任意键继续……\n");
				   getch();
				   system("cls");
				   break;
			case 5:return;
		}
	}	
}