数据结构(含课程设计)·平时作业2020春华南理工大学网络教育答案

数据结构平时作业

1.简述单链表设置头结点的主要作用。

答：设置头结点是为了保证处理第一个节点和后面的节点的时候设计的算法相同，实现程序的高效性

2. 简述线性表的顺序和链式两种存储结构各自的主要特点。 答：

顺序存储结构的主要特点是：

（1）结点中只有自身的信息域，没有关联信息域。因此，顺序存储结构的存储密度大、存储空间利用率高。更多作业加 威（yaoyao9894）

（2）通过计算地址直接访问任何数据元素，即可以随机访问。 （3）插入和删除操作会引起大量元素的移动。 链式存储结构的主要特点是：

（1）结点除自身的信息域外，还有表示关联信息的指针域。因此，链式存储结构的存储密度小、存储空间利用率低。 （2）在逻辑上相邻的结点在物理上不必相邻，因此，不可以随机存取，只能顺序存取。 （3）插入和删除操作方便灵活，不必移动结点只需修改结点中的指针域即可。

3. 说明在线性表的链式存储结构中，试述头结点,首元结点,头指针这三个概念的区别. 答：（1）头结点：是为了方便操作链表而附设的,头结点数据域通常用来保存跟链表有关的信息,比如链表的长度；

首元结点：就是链表里“正式”的第一个结点,即链表的开始结点；

头指针：头指针是指向链表的基地址。如果链表存在头结点则头指针就是指向头结点的地址,反之指向首元结点的地址。

（2）头结点、首元结点、头指针区别为：性质不同、目的不同、存在情况不同。

4. 设计一个算法，将元素x插入到一个有序（从小到大排序）顺序表的适当位置上，并保持有序性。 答：

#include

2 #include 3

4 #define LIST_INIT_SIZE 100 5 #define LISTINCREMENT 10 6 typedef struct 7 {

8 int *elem;//存储空间基址 9 int length ; 10 int listsize; 11 }SqList; 12

13 void InitList(SqList *L) 14 {

15 L->elem = (int *)malloc(LIST_INIT_SIZE*sizeof(int));//创建一个空列表

16 L->length = 0;//空表长度为0

17 L->listsize =LIST_INIT_SIZE;//初始存储容量 18 19 } 20

21 void InputData(SqList *L) 22 { 23

24 int n; 25 int *p;

26 p = L->elem;

27 printf(\请输入列表元素个数：\ 28 scanf(\

29 /*进行判断，是否超过列表长度*/

30 if(n>L->listsize)//超过存储容量，再分配空间 31 {

32 L->elem = (int*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(int));//再分配空间

33 L->listsize +=(n+LISTINCREMENT); 34 while(n!=0) 35 {

36 scanf(\ 37 p++; 38 n--;

39 L->length++; 40 } 41 } 42 else 43 { 44

45 while(n!=0) 46 {

47 scanf(\ 48 p++; 49 n--;

50 L->length++; 51 } 52 } 53 } 54

55 void DisplayList(SqList *L)//显示顺序列表 56 57 { 58

59 int i;

60 int *p = L->elem;

61 for(i = 0; ilength; i++) {

63 printf(\ 64 p++; 65 } 66 67 } 68

69 void InsertElem(SqList *L,int e)//往顺序表中插入一个元素，使其递增有序 70 {

71 //进行溢出判断

72 if(L->length+1>L->listsize)//在分配内存空间 73 {

74 L->elem = (int*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(int));//再分配空间

75 L->listsize +=(LISTINCREMENT); 76 }

77 if(L->length == 0)//如果列表为空 78 printf(\ 79 int *p = L->elem;

80 int *p_last = L->elem+L->length-1; 81 /* 先查找插入元素的位置*/ 82 while(e > *p&&p

84 p++; 85 }

86 /*p为元素的插入位置,p及后面的元素依次往后移动*/ 87 int *q ;

88 for(q = (L->elem)+(L->length)-1;q>=p;q--) 89 {

90 *(q+1) = *q; 91 }

92 *p=e;

93 L->length++; 94 } 95

96 int main() 97 {

98 SqList L; //定义一个顺序表 99 InitList(&L);//初始化

100 InputData(&L);//输入数据 101 DisplayList(&L);//显示数据