第1部分 线性表

此笔记记录了自己在学习本书的时候，记录一些知识点，让自己有个充实的学习过程，感谢阅读。
参考书：《数据结构（C语言）》–严蔚敏等编著，清华大学出版社。

一、数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素的集合；数据结构可分为线性结构和非线性结构；其中又可分为：

• 线性结构包括：
  1、线性表
  2、栈
  3、队列
  4、数组、广义表
• 非线性结构包括：
  1、树，二叉树
  2、图
  3、网等

在这里我们可以记住的是，线性结构是一对一的关系，而非线性结构是一对多、多对多的关系。数据元素之间的关系就称为结构。线性表是最常用的且最简单的一种数据结构，线性结构的特点有：

• 存在唯一的一个被称为“第一个”的数据元素（头）；
• 存在唯一的一个被称为“最后一个”的数据元素（尾）；
• 除了第一个外，集合中的每一个元素均只有一个前驱；
• 除了最后一个外，集合中的每一个元素均只有一个后继。

线性表可分为 链式 和 顺序 存储，因为两者之间的存储方式不一样，在之后的栈，队列都可使用两种存储结构进行表示与实现。

顺序存储优缺点：
优点：

1、逻辑相邻，物理相邻；
2、可以随机存取任意元素（一维数组）；
3、存储空间使用紧凑，存储密度大（存储密度=1）

缺点：

1、插入删除操作需移动大量元素；
2、预先分配的空间需按最大分配空间分配，空间利用不充分（未使用的空间搁置）

链式存储优缺点：
优点：

1、节点空间可以动态申请分配或释放节点；
2、按逻辑次序靠指针指示，插入删除操作无需移动大量元素；
3、节约大量空间

缺点：

1、存储密度小（存储密度<1)；
2、分配的指针域还需要额外的存储空间

二、线性表的顺序存储-插入操作

插入思想：

（1）、判断插入的位置是否合法；
（2）、判断顺序表是否为满；
（3）、将要插入的第i位之后的元素向后移，为了空出第i的位置；
（4）、将e值插入到i位置

#include "stdio.h"
#include "stdlib.h"
#define 	ERROR	0
#define		OK		1
#define 	TRUE	1
#define		FALSE	0
#define		OVERFLOW	-2
#define 	LIST_INIT_SIZE	100
#define		LISTINCREMENT	10typedef int Status;
typedef int ElemType;
typedef struct LNode {ElemType *elem;		//存储空间基地址int length;		//当前长度int listsize;	//当前分配的存储容量(以sizeof(ElemType)为单位)
} SqList;Status InitList_Sq(SqList &L);
//初始化创建一个的顺序表L
Status InitList_Sq(SqList &L) {L.elem = (ElemType *) malloc (LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)	exit(OVERFLOW);		//判存储分配情况L.length=0;		//空表L.listsize=LIST_INIT_SIZE;		//定义初始容量return OK;
}Status ListAdd_Sq(SqList& L,int n);
//实现顺序表的添加
Status ListAdd_Sq(SqList& L,int n) {if (L.length+1 >= L.listsize) {		//当线性表长度已经大于存储空间，就增空间ElemType* newbase = (ElemType*) realloc (L.elem,(L.listsize + LISTINCREMENT) * sizeof(ElemType)); //每次多分配十个if(!newbase) exit(OVERFLOW); 	//判存储分配情况L.elem = newbase;L.listsize += LISTINCREMENT;}for(int i=1; i<=n; i++){int num = L.length;L.elem[num] = i;L.length++;}return OK;
}Status ListInsert_Sq(SqList &L,int i,ElemType e);
//在L中的第i个位置之前插入新的元素e
Status ListInsert_Sq(SqList &L,int i,ElemType e) {
//i的合法值为1<=i<=ListLength_Sq(l)+1if(i<1||i>L.length+1) return ERROR; 	//当i小于1或者i大于顺序线性表L的值，则不合法。当i等于L.length时，表示插入到线性表结尾if(L.length >=L.listsize) {  	//当线性表长度已经大于存储空间，就分配更多的空间ElemType* newbase = (ElemType*)realloc(L.elem,(L.listsize + LISTINCREMENT)*sizeof(ElemType)); 	//每次多分配十个if(!newbase)exit(OVERFLOW);L.elem = newbase;L.listsize += LISTINCREMENT;}/*ElemType* q = &(L.elem[i-1]);   //q为插入位置的地址，i-1是因为数组下标从零开始for (ElemType* p = &(L.elem[L.length - 1]); p >= q; --p)*(p + 1) = *p;*q = e;++L.length;*/for(int j=L.length-1; j>=i-1; j--)L.elem[j+1] = L.elem[j];	//往后赋值(后移)  L.elem[i-1] = e;	//将e值赋值到i-1的位置 L.length++; return OK;
}Status ListDelete_Sq(SqList &L,int i,ElemType e);
//在L中删除第i个元素，并用e返回其值
Status ListDelete_Sq(SqList &L,int i,ElemType e){if ((i < 1) || (i > L.length)) return ERROR;	//删除位置i不合法 ElemType* p = &(L.elem[i - 1]);     //p为被删除元素的位置e = *p;     //被删除元素的值赋给eElemType* q = L.elem + L.length - 1; 	//表尾元素的位置for(p++; p<=q; p++)   //因为p为被删除元素的位置，所以要从被删除元素的后一位开始往前面移动 *(p - 1) = *p;L.length--;return OK;
}Status LocateElem_Sq(SqList L, int n,ElemType e);
//在L中查找第n个与e相等的值，如果有则返回其在线性表中的位置，否则返回0
Status LocateElem_Sq(SqList L, int n,ElemType e){for(int i=0; i<L.length; i++){if(L.elem[i]==e) return i+1;	//往后找，一直找到与e匹配的值得位置 } return OK;
}Status Print_Sq(SqList L);
//打印输出线性表元素的值 
Status Print_Sq(SqList L){if (!L.elem) return ERROR;	//空表返错 for (int i=0; i<L.length; i++){if (i < L.length-1)printf("%d,", L.elem[i]);elseprintf("%d",L.elem[i]);	//在这里是因为最后一个元素不需要打印逗号; }return OK;
}int main(void) {SqList L;int i,e;InitList_Sq(L);		//初始化顺序表 ListAdd_Sq(L,5); 	//演示----使用顺序初始化12345 printf("请输入插入的位置及其值：");scanf("%d %d",&i,&e);if(ListInsert_Sq(L,i,e)){Print_Sq(L);}else{printf("插入位置不合法\n");}return 0;
}

实现简单操作为：

顺序表的删除、查找操作请看下一节！
有问题麻烦大家提一下谢谢^_^