赞
踩
前言
学习所记录,如果能对你有帮助,那就泰裤辣。
目录
线性表是具有相同数据类型的n (n>=0)个数据元素的有限序列,其中n为表长,当n = 0时线性表是一个空表。若用 L 命名线性表,则其一般表示为
L= (A1, A2, ... , Ai, Ai+1.…. , An)
注
1.Ai 是线性表中的 “ 第 i 个” 元素线性表中的位序( 位序从1开始,数组下标从0开始 )
2.A1 是表头元素 ; an 是表尾元素。
3.除第一个元素外,每个元素有且仅有一个直接前驱;除最后一个元素外,每个元素有且仅有一个直接后继
基本操作主要包括 : 创建、销毁、增删改查
lnitList(&L): | 初始化表。构造一个空的线性表L,分配内存空间。 |
DestroyList(&L): | 销毁操作。销毁线性表,并释放线性表L所占用的内存空间。 |
ListInsert(&L,i,e): | 插入操作。在表L中的第i个位置上插入指定元素e。 |
ListDelete(&L,i,&e) | ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素,并用e返回删除元素的值。 |
LocateElem(Le): | 按值查找操作。在表L中查找具有给定关键字值的元素。 |
GetElem(L,i): | 按位查找操作。获取表L中第i个位置的元素的值。 |
Length(L): | 求表长。返回线性表L的长度,即L中数据元素的个数。 |
PrintList(L): | 输出操作。按前后顺序输出线性表L的所有元素值。 |
Empty(L): | 判空操作。若L为空表,则返回true,否则返回false。 |
顺序表――用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中,元素之间的关系由存储单元的邻接关系来体现。
- #include <stdio.h>
- #define MaxSize 10 //定义最大长度
- typedef struct{
- int data[MaxSize];
- int length; //当前长度
- }SqList;
- // 初始化顺序表
- void InitList(SqList &L){
- for(int i=0; i<MaxSize ; i++)
- L.data[i] = 0 ; //设置默认值为0
- L.length = 0 ;
- }
-
- int main(){
- SqList L; //声明顺序表
- InitList(L);
- return 0;
- }
C malloc 、frree 函数
C++ new 、delete 关键字
- #include <stdio.h>
- #include <stdlib.h>
- #define InitSize 10 //定义默认最大长度
- typedef struct{
- int *data; //指示动态分配数组的指针
- int MaxSize; //顺序表的最大容量
- int length; //当前长度
- }SqList;
- // 初始化顺序表
- void InitList(SqList &L){
- //申请存储空间
- L.data = (int*)malloc(InitSize*sizeof(int));
- L.length = 0;
- L.MaxSize = InitSize;
- }
- //增加动态数组的长度
- void IncreaseSize(SqList &L,int len){
- int *p = L.data ;
- L.data = (int *)malloc((L.MaxSize+len)*sizeof(int));
- for( int i=0 ; i<L.length ; i++ ){
- L.data[i] = p[i]; //将数据复制到新区域
- }
- L.MaxSize = L.MaxSize+len;//顺序表最大长度增加len
- free(p); //释放原来的内存空间
- }
-
- int main(){
- SqList L; //声明顺序表
- InitList(L);//初始化顺序表
- printf("%d\n",L.MaxSize);
- IncreaseSize(L,5);//增加数组长度
- printf("after:%d\n",L.MaxSize);
-
- system("pause");
- return 0;
- }
- 随机访问,即可以在O(1)时间内找到第 i 个元素。
- 存储密度高,每个节点只存储数据元素
- 拓展容量不方便(即便采用动态分配的方式实现,拓展长度的时间复杂度也比较高)
- 插入、删除操作不方便,需要移动大量元素
插入
- #include <stdio.h>
- #define MaxSize 10
-
- //定义顺序表
- typedef struct{
- int data[MaxSize]; //数据
- int length; //当前长度
- }SqList;
- //将e插入到顺序表L的第i处
- bool ListInsert(SqList &L,int i,int e){
- if(i<1 || i<L.length+1) //判断i的范围是否有效
- return false;
- if(L.length>= MaxSize) //当前存储空间已满,不能插入
- return false;
- for(int j=L.length; j>=i ; j--)//将第i个以及之后的元素后移
- L.data[j] = L.data[j-1];
- L.data[i-1] = e;
- L.length++;
- return true;
- }
删除操作
- //删除顺序表中的第i个元素
- bool ListDelete(SqList &L,int i ,int &e){
- if(i<1 || i>L.length) //判断i的范围是否合理
- return false;
- e = L.data[i-1]; //将被删除的值赋给e
- for(int j=i-1 ; j<L.length ;j++ ){ //元素前移
- L.data[j] = L.data[j+1];
- }
- L.length--;
- return true;
- }
- //按位查找:获取表L中第i个位置的元素的值
- int GetElem(SqList L,int i){
- return L.data[i-1];
- }
- //按值查找:在表L中查找具有给定关键字值的元素,并返回对应位序
- int LocateElem(SqList L,int e){
- for(int i=0;i<L.length;i++)
- if(L.data[i]==e)
- return i+1;
- return 0; //查找失败
- }
优点:不要求大片连续空间,改变容量方便。
缺点:不可随机存取,要耗费一定空间复杂度。
注意:如无特殊要求,一般视为带头结点的单链表来处理
- #include <stdio.h>
- #include <stdlib.h>
- //不带头结点的单链表
- typedef struct LNode{
- int data;
- struct LNode *next;
- }LNode,*LinkList;
-
- //初始化一个空的单链表
- bool InitList(LinkList &L){
- L = NULL; //空表,无结点,防止脏数据
- return true;
- }
-
- //判断单链表是否为空
- bool Empty(LinkList L){
- if(L == NULL )
- return true;
- else
- return false;
- }
-
- void test(){
- LinkList L;
- InitList(L);
- }
- #include <stdio.h>
- #include <stdlib.h>
-
- typedef struct LNode{
- int data;
- //struct
- LNode *next;
- }LNode,*LinkList;
-
- //初始化单链表
- bool InitList(LinkList &L){
- L = (LNode *) malloc(sizeof(LNode));//分配一个头结点
- if(L ==NULL)
- return false;
- L->next = NULL;
- return true;
- }
-
- int main(){
- LinkList L; //声明一个单链表指针
- InitList(L);
-
- system("pause");
- return 0;
- }
比较
不带头结点,写代码更麻烦
对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑
对空表和非空表的处理需要用不同的代码逻辑
带头结点
- //在第i个位置插入元素e
- bool ListInsert(LinkList &L ,int i, int e){
- if(i<1)
- return false;
- LNode *p; //指针指向当前扫描到的结点
- int j=0; //当前p指向的是第几个结点
- p = L;
- while (p!=NULL && j<i<1){ //循环找到第i-1个结点
- p=p->next;
- j++;
- }
- if(p==NULL)
- return false;
- //开始插入操作
- LNode *s = (LNode *)malloc(sizeof(LNode));//申请空间
- s->data = e;
- s->next = p->next;
- p->next = s;
- return true;
- }
不带头结点
- //在第i个位置插入元素e
- bool ListInsert(LinkList &L ,int i, int e){
- if(i<1)
- return false;
- //插入第一个结点
- if(i==1){
- LNode *s=(LNode *)malloc(sizeof(LNode));
- s->data = e;
- s->next = L;
- L = s;
- return true;
- }
-
- LNode *p; //指针指向当前扫描到的结点
- int j=0; //当前p指向的是第几个结点
- p = L;
- while (p!=NULL && j<i<1){ //循环找到第i-1个结点
- p=p->next;
- j++;
- }
- if(p==NULL)
- return false;
- //开始插入操作
- LNode *s = (LNode *)malloc(sizeof(LNode));//申请空间
- s->data = e;
- s->next = p->next;
- p->next = s;
- return true;
- }
- //后插操作:在p结点之后插入元素e
- bool InsertNextNode (LNode *p,ElemType e){
- if(p==NULL)
- return false;
- LNode *s = (LNode *)malloc(sizeof(LNode));
- if(s==NULL) //内存分配失败
- return false;
- s->data = e;
- s->next = p->next;
- p->next = s; //将结点s保存数据元素e
- return true;
- }
-
- //在第i个位置插入元素e(带头结点)
- bool ListInsert(LinkList &L,int i,ElemType e){
- if(i<1)
- return false;
- LNode *p;
- int j =0;
- p=L;
- while(p!=NULL && j<i-1){
- p=p->next;
- j++;
- }
- InsertNextNode(p,e);
- }
- //前插操作:在p结点之前插入元素e
- bool InsertPriorNode(LNode *p,ElemType e){
- if(p==NULL)
- return false;
- LNode *s = (LNode *)malloc(sizeof(LNode));
- if(s==NULL)
- return false;
- s->next = p->next;
- p->next = s; //将新结点连到p之后
- s->data = p->data; //将p中的元素复制到s中
- p->data = e; //p中元素覆盖为e
- return true;
- }
- //按位序删除(带头结点)
- bool ListDelete(LinkList &L,int i,ElemType &e){
- if(i<1)
- return false;
- LNode *p;
- int j=0;
- p = L;
- while(p!=NULL && j<i-1){//将p指针定位到第i-1个结点
- p=p->next;
- j++;
- }
- if(p==NULL)//i值不合法
- return false;
- if(p->next == NULL)
- return false;
- LNode *q = p->next; //令q指向被删除结点
- e = q->data; //用e返回元素的值
- p->next=q->next; //将*q结点从链中“断开”
- free(p); //释放结点的存储空间
- return true;
- }
即将p后继结点的值赋给p,再将p的后继删除。
- //删除指点结点p
- bool DeleteNode(LNode *p){
- if(p==NULL)
- return false;
- LNode *q=p->next; //令q指向*p的后继结点
- p->data=p->next->data; //和后继结点交换数据域
- p->next=q->next; //将*q结点从链中“断开”
- free(q); //释放后继结点的存储空间
- return true;
- }
- //按位查找,返回第i个元素(带头结点)
- LNode * GetElem(LinkList L,int i){
- int j=1;
- LNode *p=p->next;
- if(i==0)//若获取的是第一个结点
- return L;
- if(i<1)//若链表L中没有结点
- return NULL;
- while(p!=NULL && j<i){
- p=p->next;
- j++;
- }
- return p;
- }
- //按位查找,找到数据域==e的结点
- LNode * LocateElem(LinkList L,ElemType e){
- LNode *p = L->next;
- //从第1个结点开始查找数据域为e的结点
- while(p!=NULL && p->data!=e)
- p=p->next;
- return p; //若找到则返回结点指针,否则返回NULL
- }
- //表的长度
- int length(LinkList L){
- int len=0;
- LNode *p =L;
- while(p->next!=NULL){
- p = p->next;
- len++;
- }
- return len;
- }
- //尾插法
- bool List_TailInsert(LinkList &L){
- int x;
- L = (LinkList)malloc(sizeof(LNode));
- LNode *s,*r=L; //r为表尾指针
- scanf("%d",&x); //输入结点的值
- while(x!=9999){ //输入9999则结束输入
- //在r结点之后插入元素x
- s = (LNode*)malloc(sizeof(LNode));
- s->data = x;
- r->next = s;
- r=s; //确保r为表尾指针
- scanf("%d",&x);
- }
- r->next=NULL;
- return L;
- }
即每次插入一个元素都插入到单链表头结点后面。
- LinkList List_HeadInsert(LinkList &L){
- LNode *s;
- int x;
- L = (LinkList)malloc(sizeof(LNode));//创建头结点
- scanf("%d",&x); //输入结点的值
- while(x!=9999){ //输入9999则结束输入
- //在头结点之后插入元素x
- s = (LNode*)malloc(sizeof(LNode));
- s->data = x;
- s->next = L->next;
- L->next = s;
- scanf("%d",&x);
- }
- return L;
- }
与单链表相比,多了个前驱指针,可以逆向检索
- #include <stdio.h>
- #include <stdlib.h>
-
- #define ElemType int
-
- typedef struct DNode{
- ElemType data;
- struct DNode *prior,*next;
- }DNode,*DLinklist;
-
- //初始化双链表(带头结点)
- bool InitDLinkList(DLinklist &L){
- L = (DNode *)malloc(sizeof(DNode));
- if(L==NULL) //内存不足,分配失败
- return false;
- L->prior = NULL; //头结点的prior永远指向NULL
- L->next = NULL;
- return true;
- }
-
- int main(){
- //初始化双链表
- DLinklist L;
- InitDLinkList(L);
-
- return 0;
- }
- //在p结点后插入s结点
- bool InsertNextDNode(DNode *p,DNode *s){
- if(p==NULL || s==NULL)
- return false;
- s->next = p->next;
- if(p->next != NULL) //如果p结点有后继结点
- p->next->prior = s;
- s->prior = p;
- p->next = s;
- return true;
- }
- //删除p结点的后继结点
- bool DeleteNextDNode(DNode *p){
- if(p==NULL)
- return false;
- DNode *q = p->next; //找到p的后继结点q
- if(q==NULL) //p没有后继结点q
- return false;
- p->next = q->next;
- if(q->next!=NULL) //q结点不是最后一个结点
- q->next->prior = p;
- free(q); //释放结点空间
- return true;
- }
将表尾指针指向头结点
- #include <stdio.h>
- #include <stdlib.h>
- #define ElemType int
-
- typedef struct LNode{ //定义单链表结点类型
- ElemType data; //每个节点存放一个数据元素
- struct LNode *next; //指针指向下一个节点
- }LNode,*LinkList;
-
- //判断循环单链表是否为空
- bool Empty( LinkList L) {
- if(L->next == L)
- return true;
- else
- return false;
- }
-
- //判断结点p是否为循环单链表的表尾结点
- bool isTail( LinkList L, LNode *p){
- if (p->next==L)
- return true;
- else
- return false;
- }
-
- //初始化一个循环单链表
- bool InitList(LinkList &L) {
- L = (LNode *) malloc(sizeof( LNode) );//分配一个头结点
- if (L==NULL) //内存不足,分配失败
- return false;
- L->next = L; //头结点next指向头结点
- return true;
- }
双链表:
表头结点的prior指向NULL;表尾结点的next指向NULL
循环双链表:
表头结点的prior指向表尾结点;表尾结点的next指向头结点
- #include <stdio.h>
- #include <stdlib.h>
- #define ElemType int
-
-
- typedef struct DNode{
- ElemType data;
- struct DNode *prior ,*next;}DNode,*DLinklist;
-
-
- //初始化空的循环双链表
- bool InitDLinkList(DLinklist &L){
- L = ( DNode *) malloc(sizeof( DNode) );//分配一个头结点
- if (L==NULL) //内存不足,分配失败
- return false;
- L->prior = L; //头结点的prior指向头结点
- L->next = L; //头结点的next指向头结点
- return true;
- }
- //判断循环双链表是否为空
- bool Empty(DLinklist L) {
- if(L->next == L)
- return true;
- else
- return false;
- }
-
- //判断结点p是否为循环链表的表尾结点
- bool isTail(DLinklist L,DNode *p){
- if( p->next==L)
- return true;
- else
- return false;
- }
-
- void testDLinkList() {
- //初始化循环双链表
- DLinklist L;
- InitDLinkList(L);
- // ...后续代码...
- }
在p结点后插入新结点、删除p结点后面的结点时不用考虑p后继结点是否为空的问题
删除
- //删除p结点的后继结点
- bool DeleteNextDNode(DNode *p){
- if(p==NULL)
- return false;
- DNode *q = p->next; //找到p的后继结点q
- //注释的内容为双链表所需进行的条件判断
- //if(q==NULL) //p没有后继结点q
- // return false;
- p->next = q->next;
- //if(q->next!=NULL) //q结点不是最后一个结点
- // q->next->prior = p;
- free(q); //释放结点空间
- return true;
- }
插入
- //在p结点后插入s结点
- bool InsertNextDNode(DNode *p,DNode *s){
- if(p==NULL || s==NULL)
- return false;
- s->next = p->next;
- //注释的内容为双链表所需进行的条件判断
- // if(p->next != NULL) //如果p结点有后继结点
- // p->next->prior = s;
- s->prior = p;
- p->next = s;
- return true;
- }
单链表:各个结点在内存中随机存储。
静态链表:分配一整片连续的内存空间,各个结点集中存储。用数组的方式实现的链表。
- #define MaxSize //静态链表的最大长度
- typedef struct { //静态链表结构类型的定义
- int data; //存储数据元素
- int next; //下一个元素的数组下标
- }SLinkList[MaxSize];
基本操作的实现逻辑
初始化静态链表:
把a[o] 的next 设为1
把其他结点的next设为一个特殊值用来表示结点空闲,如-2
查找:
从头结点出发挨个往后遍历结点插入位序为i的结点:
①找到一个空的结点,存入数据元素②从头结点出发找到位序为i-1的结点
③修改新结点的next
④修改i-1号结点的next
删除某个结点:
①从头结点出发找到前驱结点②修改前驱结点的游标
③被删除结点next设置一个特殊值以表示已经被删除
都属于线性表,都是线性结构
顺序表(顺序存储):
优点:支持随机存取、存储密度高
缺点:大片连续空间分配不方便,改变容量不方便链表(链式存储):
优点:离散的小空间分配方便、改变容量方便
缺点:不支持随机存取、存储密度低
创销、增删改查
创建
顺序表:
需要预分配大片连续空间。若分配空间过小,则之后不方便拓展容量;若分配空间过大,则浪费内存资源
链表:只需分配一个头结点(也可以不要头结点,只声明一个头指针),之后方便拓展
销毁
顺序表:
静态分配:静态数组 -->系统自动回收空间
动态分配:动态数组( malloc、 free) --> 需要手动free
链表:依次删除各个结点( free)
增删
顺序表:
插入/删除元素要将后续元素都后移/前移
链表:插入/删除元素只需修改指针即可
查
顺序表:
按位查找:O(1)
按值查找:O(n)若表内元素有序,可在O()时间内找到
链表:按位查找:O(n)
按值查找:O(n)
综上所述
表长难以预估、经常要增加/删除元素—―链表
表长可预估、查询(搜索)操作较多――顺序表
开放式问题的答题思路:
问题:请描述顺序表和链表的bla bla bla....
交规线性表时,用顺序表还是链表好?(6分)
一一
顺序表和链表的逻辑结构都是线性结构,都属于线性表。
但是二者的存储结构不同,顺序表采用顺序存储...(特点,带来的优点缺点);链表采用链式存储...(特点、导致的优缺点)。
由于采用不同的存储方式实现,因此基本操作的实现效率也不同。当初始化时...;当插入一个数据元素时...;当删除一个数据元素时...;当查找一个数需元素时...
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。