考研笔记 | 数据结构 §2. 线性表

发表于 分类于 阅读次数： 本文字数： 3.3k 阅读时长 ≈ 3 分钟

  1. 线性表是具有相同数据类型的 n（n≥0）个数据元素的有限序列。

  2. 特点：

    1. a₁是唯一的 “第一个” 数据元素，又称 “表头元素”
    2. an 是唯一的 “最后一个” 数据元素，又称 “表尾元素”
    3. 除 a₁外每个元素有且仅有一个直接前驱 ;
    4. 除 an 外每个元素有且仅有一个直接后继。

  3. 定义：“数组 + 长度”

    1
    2
    3
    4
    5
    #define MaxSize=50
    typedef struct{    
    ElemType data{MaxSize};
    int length;
    }Sqlist;//静态分配
    1
    2
    3
    4
    5
    6
    #define InitSize 100
    L.data=(ElemType*)Malloc sizeof(ElemType)*InitSize;
    typedef struct{
    	ElemType *data;
    	int MaxSize,length;
    }SeqList;//动态分配

  4. 链表的基本操作

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    InitList(&L)//初始化表
    Length(L)//求表长
    LocateElem(L,e)//按值查找
    GetElem(L,i)//按位查找
    ListInsert(&L,i,e)//按位插入
    ListDelete(&L,i,&e)//按位删除
    PrintList(L)//遍历并打印
    Empty(L)//判定表不空
    PriorElem(L,e,&Prior)NextElem(L,e,&next)//求前驱、后继
    DestoryList(&L)//销毁链表

  5. 在第 i 处插入新元素 e

    1
    2
    3
    4
    5
    6
    7
    8
    9
    bool ListInsert(Sqlist &L,int i,ElemType e){
    	if(L. length>=MaxSize||i<1||i>L. length+1)
    		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;
    }//最好O(1)，最坏O(n)，平均O(n)

  6. 删除第 i 个位置的元素，将该元素用 e 返回

    1
    2
    3
    4
    5
    6
    7
    8
    9
    bool ListDelete(Sqlist &L,int i,int &e){
    	if(i>L. length||i<1)
    		return flase;
    	e=L. data[i-1];
    	for(int j=i;j<length;j++)//将i后元素前移
    		L. data[j-1]=L. data[j];
    	L. length--;
    	return true;
    }//最好O(1)，最坏O(n)，平均O(n)

  7. 单链表：线性表的链式存储。

  8. 对链表的结点，除了存放元素自身，还要存放指向后继的指针。单链表结点

  9. 类型定义：“数据 + 指针”

    1
    2
    3
    4
    typedef struct LNode{
    	ElemType data;//数据域
    	Struct LNode *next;//指针域
    }LNode,*Linklist;

  10. 访问、遍历数据

    1
    2
    3
    4
    5
    6
    7
    void VisitLinklist(Linklist){
     P=L->next;
     while(p!=NULL){
      visit(P->data);//主体，可换做其他，如，print(P->data);
      P=P->next;
     }
    }

  11. 头插法建立单链表

    头插法建立单链表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    Linklist CreatList(Linklist &L){
    	LNode *S,int x;
    	L=(Linklist)malloc(sizeof(LNode));//头结点
    	L->next-NULL;//空表
    	scanf("%d",&x);
    	for(i=0;i<9999;i++){
    		S=(LNode*)malloc(sizeof(LNode));
    		S->data=x;S->next=L->next;L->next=S;
    		scanf("%d",&x);
    	}
    	return L;
    }//读入数据顺序与生成链表中元素顺序相反，O(n)

  12. 尾插法建立单链表

    尾插法建立单链表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    Linklist CreatList(Linklist &L){
    	int x;
    	L=(Linklist)malloc(sizeof(LNode));//头结点
    	LNode *S,*r=L;//r为表尾指针
    	Scanf("%d",&x);
    	for(i=0;i<9999;i++){
    		S=(LNode*)malloc(sizeof(LNode));
    		S->data=x;r->next=S;r=S;
    		scanf("%d",&x);
    	}
    	r->next=NULL;
    	return L;
    }//得到的顺序与原顺序相同

  13. 按序号查找结点值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    LNode *GetElem(Linklist L,int i){
    	int j=1;LNode *P=L-next;
    	if(i==0) return L;
    	if(i<1) return NULL;
    	while(P&&j<i){
    		P=P->next;
    		j++;
    	}
    	return P;
    }//O(n)

  14. 按值查找：查找给定值 e

1
2
3
4
5
6
7
8
9
10
LNode *GetElem(Linklist L,int i){
    int j=1;LNode *P=L-next;
    if(i==0) return L;
    if(i<1) return NULL;
    while(P&&j<i){
        P=P->next;
        j++;
    }
    return P;
}//O(n)

  1. 插入结点

    单链表插入结点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    bool ListInsert(Linklist &L,int i,ElemType x){
    	P=L;j=0;
    	while(P&&j<i-1){
    		P=P->next;j++;
    	}
    	if(P&&j==i-1){
    	  S=(Linklist)malloc(sizeof(LNode));
    	  S->data=x;S>next=P->next;P>next=S;
    	  return ture;
    	}
      else return flase;
    }//O(n),若给定结点后插入O(n)

  2. 删除结点

    单链表删除结点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    bool ListDelete(Linklist &L,int &x){
    	P=L;j=0;
    	while(P&&j<i-1){
    		P=P->next;j++;
    	}
    	if(P&&j==i-1&&P-next){
    		S=P->next;P-next=S->next;x=S-next;
    		free(S);
    		return true;
    	}
    	else return flase;
    }//O(n)

  3. 双链表：定义

    双链表结点

    1
    2
    3
    4
    typedef struct DNode{
    	ElemType data;
    	Struct DNode *Prior,*next;
    }DNode,*DLinklist;

  4. 静态链表：定义

    静态链表

    1
    2
    3
    4
    5
    #define MaxSize 50
    typedef struct{
    	ElemType data;
    	int next;
    }SLinkList[MaxSize]//用数组存储，以next=-1作结束标志

  5. 顺序存储的特点是利用物理上相邻表达元素之间的关系，
    链式存储是通过指针表示元素之间的关系。