Cammie Phan

最紧要好玩

9
文章
4
分类
10
标签

线性结构

notes
  |  
 阅读次数

线性表的概念
顺序表
链表
顺序表与链表
线性表的应用

线性表的概念

线性表是n(n>=0)个具有相同特性的数据元素a1,a2,…,an的有序序列。

特点：

  • 所有元素具有相同的特性，属于相同的数据对象，有相同的数据类型； //即均一性
  • 有唯一的表头元素a1；
  • 有唯一的表尾元素a2；
  • 除了a1外，其他元素都有唯一的前驱；
  • 除了an外，其他元素都有唯一的后继； //序偶性

在线性表中，每条数据元素可以由若干个数据项构成，这种情况下，通常把数据元素称为记录

线性表示例

顺序表

顺序表：将线性表中的元素相继存储在一段连续的存储空间中
线性表中的第i+1个元素与第i个元素之间的存储位置关系满足关系式：LOC(ai+1) = LOC(ai) + k,k代表每个数据元素占用k个存储单元

动态数组

由于在实际开发中，实际需要的数组空间是无法预料的，开辟过大的存储空间又会造成冗余，所以常常需要使用动态数组

  • 静态数组：程序运行过程中，数组的大小是无法改变的
  • 动态数组：数组占用的内存空间是可以在程序运行过程中根据需要而设定的，通过指向该内存的指针来访问

动态数组的本质：通过指向数组的指针变量来访问（利用了C语言的指向数组的指针可以当成数组名来使用的特点） 

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
#include "stdio.h"
#include "malloc.h"
#include "stdlib.h"
void main()
{
	int *p = NULL, num, i;
	printf("how many numbers are you going to input:");
	scanf("%d",&num);
	//申请动态数组使用的内存块
	p = (int *)malloc(num*sizeof(int));		//返回新分配内存块的起始位置
					//使用malloc 函数必须强制类型转换为定义的指针的类型
	if(p==NULL)
	{
		printf("分配内存失败");
		exit(0);			//终止程序
	}
	printf("please input %d numbers:",num);
	for(i=0;i<num;i++)
	{
		scanf("%d",&p[i]);
	}
	
	printf("the numbers you input are: \n");
	
	for(i=0;i<num;i++)
	{
		printf("%d",p[i]);
	}
	free(p);		//释放出malloc 申请的内存
					//如果使用了malloc必须用free释放内存
}

顺序表的基本运算

1
2
3
4
5
6
7
8
9
10
//定义结构体类型
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define ListSize 100
struct SeqList{
	int *data;		//定义动态数组
	int length;
};

初始化

1
2
3
4
5
6
7
8
9
10
11
struct SeqList InitList()
{
	struct SeqList l;
	l.data = (int*)malloc(ListSize*sizeof(int));
	if(l.data == NULL){
		printf("分配内存失败！\n");
		exit(0);
	}
	l.length = 0;
	return l;
}

按值查找

1
2
3
4
5
6
7
8
9
10
int SeqList Search(struct SeqList l,int x){
	int i = 0;
	while(i<l.length && l.data[i] != x)
	{
		i++;
	}
	if(i<l.length)
		return i;
	else return -1;
}

表的长度

1
2
3
int SeqList Length(struct SeqList l){
	return l.length;
}

提取元素

1
2
3
4
5
6
int GetData(struct SeqList l,int i){
	if(i<0 || i>=l.length){
		printf("参数i不合理\n");
		return l.data[i];
	}
}

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int Insert(struct SeqList l,int i,int x){
	int j = 0;
	if(i>=0 && i<l.length && l.length < ListSize){
		for(j=l.length-1;j>=i;j--){
			l.data[j+1]=l.data[j];
		}
		l.data[i-1] = x;
		l.length++;
		printf("插入成功\n");
		return 1;
	}
	printf("插入失败\n");
	return 0;
}

删除

1
2
3
4
5
6
7
8
9
10
11
int Delete(struct SeqList l,int i){
	if(i<0 || i>=l.length){
		printf("不存在这个元素\n");
		return 0;
	}
	else 
		for(;i < l.length;i++){
			l.data[i-1] = l.data[i];
			return 1;
		}
}

完整的程序

让计算机实现以下功能

  1. 让计算机随机产生10个随机数并保存到顺序表中
  2. 遍历顺序表，输出各个值
  3. 对产生顺序表置逆
  4. 观察置逆后的顺序表的结果
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
//2017/09/29		cammie			seqlist
#include <stdio.h>
#include <stdlib.h>
#define maxsize 10
typedef int elemtype;
struct seqlisttype{
	elemtype data[maxsize+1];
	int length;
};
//create seqlist type
void initial(struct seqlisttype &l){
	l.length = 0;
}
//initial the list 
/* 上面是静态数组，以下为动态数组
struct seqlisttype{
	elemtype *data;
	int length;
};
//create seqlist type
void initial(struct seqlisttype &l){
	l.data = (elemtype *)malloc(maxsize*sizeof(elemtype));
	if(l.data == NULL){
		printf("memory allocation failure!\n");
		exit(0);
	}
	l.length = 0;
}
//initial the list 
 */
int insert(struct seqlisttype &l,int i,int x){
	if(l.length == maxsize){
		printf("memory overflow\n");
		return 0;
	}
	if((i < 1) || (i > l.length+1)){
		printf("argument error, out of range\n");
		return 0;
	}
	for(int j = l.length;j >= i;j--){
		l.data[j+1] = l.data[j];
	}
	l.data[i] = x;
	l.length++;
	return 1;
}
//insert an element to the list
void create(struct seqlisttype &l){
	int i = 1,j;
	
	for(i = 1;i <= maxsize;i++){
		j = rand();
		insert(l,i,j);
	}
}
//create some random number to the list
/*
void create(struct seqlisttype &l){
	int i = 1,j;
	
	for(i = 1;i <= maxsize;i++){
		j = rand();
		l.data[i] = j;
		l.length++;
	}
}
*/
void view(struct seqlisttype l){
	if(l.length == 0){
	printf("the list is an empty list.\n");
	}
	else{
		printf("the list :");
		for(int i = 1;i <= maxsize;i++){
			printf("  %d",l.data[i]);
		}
		printf("\n");
	}
}
//view the list
int reverse(struct seqlisttype &l){
	int i,t;
	if(l.length == 0){
		printf("the list is empty!\n");
		return 0;
	}
	for(i = 1;2*i <= l.length;i++){
		t = l.data[i];
		l.data[i] = l.data[l.length-i+1];
		l.data[l.length-i+1] = t;
	}
	return 1;
}
//reverse the list
void main(){
	struct seqlisttype l;
	initial(l);
	int i = 1;
	while(i!=0){
		printf("press 0 to exit the program!\n");
		printf("press 1 to create a random list!\n");
		printf("press 2 to view the list!\n");
		printf("press 3 to reverse the list!\n");
		scanf("%d",&i);
		switch(i){
		case 0: exit(1);
		case 1: create(l); break;
		case 2: view(l); break;
		case 3: reverse(l); break;
		default: printf("input error!\n");
		}
	}
}

链表

链表是线性表的链式存储结构。

单链表

静态链表
循环链表
双向链表

单链表

用一组任意的存储单元存储线性表中的元素。

要点：

  • head 头指针
  • data 数据域
  • link 指针域

结点node由数据域与指针域组成。

单链表的类型定义 ：

1
2
3
4
5
struct ListNode{
	char data;
	struct ListNode *link; 		//递归
};
struct ListNode *head;

要点：

  • p-> 即指针指向的结点，p->data 即 (*p).data； p->link 即(*p).link

单链表的基本操作：

插入2

插入操作有三种情况：

  • 在第一个结点前插入
  • 在中间插入
  • 在链表末尾插入
1
2
3
//在第一个结点前插入
newnode->link = head;
head = newnode;
1
2
3
//在中间插入
newnode->link = p->link;
p->link = newnode;
1
2
3
//在链表后面插入
newnode->link = p->link;
p->link = newnode;

删除2

1
2
x = p->link->data;
p->link = p->link->link;

一个完整的程序

让计算机实现以下功能

  1. 让计算机随机产生10个随机数并保存到线性链表中
  2. 遍历线性链表，输出各个结点的值
  3. 对产生线性链表就地置逆并利用原来的结点空间储存
  4. 观察置逆后的链表的结果
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
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define len sizeof(struct node)
typedef int elemtype;
struct node{
	elemtype data;
	struct node *link;
};
//create node type
struct node* initial(){
	struct node *head;
	head = (struct node*)malloc(len);
	if(head == NULL){
		printf("memory allocation failure\n");
		exit(0);
	}
	head->link = NULL;								//NULL,not null
	return head;
}
//initial the linked list.
int insert(struct node *head,int i,elemtype x){
	struct node *p = head, *newnode;				//better to write"= head"in here than in the next line after define *p
	int j = 0;
	
	if(i<1){
		printf("error!\n");
		return 0;
	}
	while(p!=NULL && j<(i-1)){
		p = p->link;
		j++;
	}
	if(p==NULL){										//attention!it is ==,not =
			printf("the list is less than %d",i-1);
			return 0;
	}
	
	newnode = (struct node*)malloc(len);
	if(newnode == NULL){
			printf("memory allocation failure\n");
			return 0;
	}
	
	newnode->data = x;
	newnode->link = p->link;
	p->link = newnode;
	
	return 1;
}
//insert an element.
void create(struct node *head){
	int i;
	elemtype j;
	for(i=1;i<=10;i++){
		j = rand();
		insert(head,i,j);
	}
}
//create 10 random elements to the list.
void view(struct node *head){
	struct node *p;
	p = head->link;
	
	while(p!=NULL){
		printf("  %d",p->data);
		p = p->link;
	}
	printf("\n");
}
//view elements in the list.
void reverse(struct node *head){
	struct node *cp = head->link, *pp = NULL, *np;
	while(cp!=NULL){
		np = cp->link;
		cp->link = pp;
		pp = cp;
		cp = np;
	}
	head->link = pp;
}
//reverse the list.
void main(){
	int i=1;
	struct node *h;
	h = initial();
	while(i!=0){
		printf("press 0 to exit the program\n");
		printf("press 1 to create a 10 random numbers list.\n");
		printf("press 2 to view the list\n");
		printf("press 3 to reverse the list\n");
		
		scanf("%d",&i);
		
		switch(i){
			case 0: exit(0);
			case 1: create(h);break;
			case 2: view(h);break;
			case 3: reverse(h);break;
			default: printf("input error\n");
		}
	}
}

静态链表

静态链表示意图