第二章 线性表思维导图

存在唯一的一个被称为“第一个”的数据元素

存在唯一的一个被称为“最后一个"的数据元素

除第一个元素外,结构中的每个数据元素均只有一个前驱

除最后一个元素外,结构中的每个数据元素均只有一个后继

特点:逻辑上相邻的数据元素,其物理位置也是相邻的

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素,这种表示也称作线性表的顺序存储结构或顺序映像,通常称这种存储结构的线性表为顺序表。

只要确定了存储线性表的起始位置,线性表中任一元素都可随机存取,线性表的顺序存储结构是一种随机存取的存储结构

通常用数组来描述数据结构中的顺序存储结构,在C语言中可用动态分配的一维数组表示

初始化 Status InitList(SqList &L)XL.elem=new ElemType[MAXSIZE]; if(!L.elem) exit(OVERFLOW); L.length=0; return OK; }

取值 Status GetElem(SqListL,ElemType e) { int i; if(i<1||i>L.length) return ERROR; e=L.elem[i-1]; return OK; }

查找 int LocateElem(SqListL,ElemType e) { int i; for(i=0;i<L.length;i++) { if(L.elem[i]==e) return i+1; } return 0; }

插入 Status Listlnsert(SqList &L,int i ElemType e) int j; if((i<1)l(i>L.length+1))return ERROR; if(L.length==MAXSIZE) returnERROR; for(j=L.length-1;j>=1-1;j--)L.elemj+1]=L.elemj]; L.elem[i-1]=e; L.length++;return OK; } }

删除 void ListDelete(SqList &L,int i) { int j; if((i<1)川(i>L.length))printf("错误"); for(j=i;j<=L.length-1;j++) L.elem[j-1]=L.elemi]; --L.length; }

其中存储数据元素信息的域称为数据域

存储直接后继存储位置的域称为指针域。指针域中存储的信息称作指针或链

定义 typedef struct LNode{int data; struct LNode *next;}LNode,*LinkList;

初始化 Status InitList(LinkList &L) L= new LNode;L->next=NULL;return OK; } }

取值 void GetElem(LinkList L,int i,int &e) { LinkList p=L->next;int j=1; while(p&&j<i){ p=p->next; ++j; } if(!pllj>i) printf("错误"); e=p->data; }

查找 LNode *LocateElem(LinkList L,int e) LinkList p=L->next; while(p&&p->data!=e) p=p->next; return p; } }

插入 void Listlnsert(LinkList &L,int i,int e) { LinkList p=L;int j=0; while(p&&(j<i-1)) p=p->next; ++j; } if(!pllj>i-1) printf("错误"); LinkList s=(LinkList)malloc(lnm); S->data=e; s->next=p->next;p->next=s; } }

删除 void ListDelete(LinkList &L,int i) { LinkList p=Lint j=0; while((p->next)&&(j<i-1)){p=p->next; ++j; } if(!(p->next)ll(j>i-1)) printf("错误");LinkList q=p->next;p->next=q->next;delete q; }

前插法创建单链表 void CreateList_H(LinkList &L,int n,int a[]) L=new LNode; L->next=NULL; for(int i=0;i<n;i++) { LinkList p=(LinkList)malloc(lnm); p->data=a[i]; p->next=L->next; L->next=p; } }

尾插法创建单链表 void CreateList_R(LinkList &L,int n,int a[]) L=new LNode; L->next=NULL; LinkList r=L; for(int i=0;i<n;++i) LinkList p=new LNode; p->data=a[i]; p->next=NULL; r->next=p; r=p;