第二章： 线性表

2.1 线性表的定义和基本操作

2.1.1 线性表的定义

\quad 线性表： 具有相同数据类型的n个数据元素的有限序列。

\quad 注： 线性表包括顺序表和链表等。线性表是一个逻辑结构，而顺序表和链表是存储结构。

2.1.2 线性表的基本操作

\quad InitList(&L) ; 初始化。

\quad Length(L) ;求长度

\quad LocateElem(L,e) ;定位e的下标

\quad GetElem(L,i) ;查看下标i的元素

\quad ListInsert(&L,i,e) ;位置i插入e

\quad ListDelete(&L,i,&e) ;删除位置i的元素给e

\quad PrintList(L) ;打印列表

\quad Empty(L) ;判空

\quad DestroyList(&L) ;释放内存

2.2 线性表的顺序表示

2.2.1 顺序表的定义

\quad 顺序表长度固定：

1
2
3
4
5
#define MaxSize 50
typedef struct {
    Elemtype data[MaxSize];
    int length; 
}SqList;

\quad 顺序表的长度不固定：

1
2
3
4
5
#define InitSize 50
typedef struct {
    Elemtype * data;
    int MaxSize,length;
}SeqList;

\quad 初始化：

1
L.data = (Elemtype*)malloc(sizeof(Elemtype)* InitSize)
1
L.data = new ElemType[InitSize]

2.2.2 顺序表上基本的操作实现

\quad（1）插入

1
2
3
4
5
6
7
8
9
10
11
12
13
bool ListInsert(SqList &L,int i,Elemtype e)
{
    if(i<1 || i >L.length+1)
        return false;
    if(L.length >= MaxSize)
        return false;
    for(int j = L.length;j >= i;j--)
        L.data[j] = L.data[j-1];
    L.data[i-1] = e;
    L.length++;
    
    return true;
}

\quad（2）删除

1
2
3
4
5
6
7
8
9
10
11
bool ListDelete(SqList &L,int i,Elemtype &e)
{
    if(i<1 || i > L.length)
        return false;
    e = L.data[i-1];
    for(int j = i;j < L.length;j++)
        L.data[j-1] = L.data[j];
    L.length--;
    
    return true;
}

\quad（3）按值查找

1
2
3
4
5
6
7
int LocateElem(SqList L,Elemtype e){
    int i;
    for (i=0;i < L.length;i++)
        if(L.data[i] == e)
            return i+1;
    return 0;
}

2.3 线性表的链式表示

2.3.1 单链表的定义

1
2
3
4
typedef struct LNode{
    Elemtype data;
    struct LNode *next;
}LNode,*LinkList;

2.3.2 单链表上基本操作的实现

\quad（1）头插法建立单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LinkList List_HeadInsert(LinkList &L)
{
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    scanf("%d",&x);
    while(x != 999)
        s = (LNode*)malloc(sizeof(LNode));
    	s->data = x;
    	s->next = L->next;
    	L->next = s;
    	scanf("%d",&x);
    return L;
}

\quad（2）尾插法建立单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
LinkList List_TailInsert(LinkList &L)
{
    
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LNode *s, *r =L;
    L->next = NULL;
    scanf("%d",&x);
    while(x != 999)
        s = (LNode*)malloc(sizeof(LNode));
    	s->data = x;
    	r->next = s;
    	r = s;
    	scanf("%d",&x);
    r->next = NULL;
    return L;
}

\quad（3）按序号查找结点值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}

\quad（4）按值查找表结点

1
2
3
4
5
6
7
LNode * LocateElem(LinkList L,ElemType e)
{
    LNode *p = L->next;
    while(p!=NULL && p->data = e)
        p = p->next;
    return p;
}

2.3.3 双链表

（1）定义

1
2
3
4
5
typedef struct DNode
{
    ElemType data;
    struct DNode *prior,*next;
}DNode,*DLinkList;

2.3.4 链表其他变形

\quad 循环单链表与循环双链表