Scott's world.

第二讲 线性结构

Word count: 2.2kReading time: 12 min
2019/07/03 Share

第二讲 线性结构

2.1 线性表及其表示

  • 多项式的表示

    • 顺序存储结构直接表示

    • 顺序存储结构表示非零项

    • 链表结构存储非零项

  • 线性表的顺序结构存储

    • 相应实现方法

      • 初始化

        1
        2
        3
        4
        5
        6
        7
        List CreateList()
        {
        List PtrL;
        PtrL=(List)malloc(sizeof(struct LNode));
        PtrL->Last=-1;
        return PtrL;
        }
      • 查找

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        int Find(ElementType X,List PtrL)
        {
        int i=0;
        while(i<=PtrL->last&&Ptrl->Data[i]!=X)
        {
        i++;
        }
        if(i>PtrL->Last)return -1;
        else return i;
        }
      • 插入

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        void Insert(ElementType X,int i,List PtrL)
        {
        int i;
        if(PtrL->Last==MAXSIZE-1)
        {
        printf("表满");
        return;
        }
        if(i<1||i>PtrL->Last+2)
        {
        printf("位置不合法");
        }
        for(j=PtrL->Last;j>=i-1;j--)
        {
        PtrL->Data[j+1]=PtrL->Data[j];
        }
        PtrL->Data[i-1]=X;
        ptrL->Last++;
        return;
        }
      • 删除

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        void Delete(int i,List PtrL)
        {
        int j;
        if(i<1||i>PtrL->Last+1)
        {
        printf("不存在此元素");
        return ;
        }
        for(j=i;j<=PtrL->Last;j++)
        PtrL[j]=PtrL[j+1];
        PtrL->Last--;
        return;
        }
  • 线性表的链式存储结构

    • 相应操作实现

      • 求表长

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        int Length(List Ptrl)
        {
        List p=Ptrl;
        int j=0;
        while(p)
        {
        p=p->Next;
        j++;
        }
        return j;
        }
      • 创建结点

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        List createNode()
        {
        List p;
        int data;
        p=(List)malloc(sizeof(struct LNode));
        if(p==NULL)
        {
        exit(0);
        }
        p->Next=NULL;
        printf("input the value of the node: ");
        scanf("%d",&data);
        p->Data=data;
        return p;
        }
- 创建链表

  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
List createList(void)
{
List head=NULL,pre,p;
int i,j;
printf("开始建立链表,请根据提示输入数据: ");
do
{
printf("\nPlease press 'y' to insert one new node,press 'n' to finish:");
fflush(stdin);
printf("\nPlease press 'y' to insert one new node,press 'n' to finish:");
scanf("%c",&c);
if((c!='y'&&c!='Y')&&(c!='n'&&c!='N'))
{
puts("you must input 'y' or 'n' ");
continue;
}
if((c=='n'||c=='N'))
{
break;
}
p=createNode();
if(head==NULL)
{
head=p;
}else{
pre->next=p;
pre=p;
}
}while(1);
return (head);
}
- 输出链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void printList(List head)
{
List p;
p=head;
if(head==NULL)
{
printf("List is empty!\n");
return ;
}
else{
while(p!=NULL)
{
printf("%5d\n",p->data);
p=p->next;
}
}
}
- 释放内存
1
2
3
4
5
6
7
8
9
10
void deleteMemory(List head)
{
List p=head,pre=NULL;
while(p!=NULL)
{
pre=p;
p=p->next;
free(pre);
}
}
- 插入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
List insertNode(List head,List p,int pos)
{
List pre;
if(head=NULL)
{
head=p;
p->next=NULL;
}
else
{
if(pos==0)
{
p->next=head;
head=p;
}
else
{
pre=head;
for(;pre!=NULL&&pos>1;pre=pre->next,pos--);
if(pre==NULL) printf("Out the range,can't insert\n");
else
{
p->next=pre->next;
pre->next=p;
}
}
}
return head;
}
- 删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
List deleteNode(List head,int todelete)
{
List *pre,*p;
if(head==NULL)
{
printf("\n List is empty\n");
return ;
}
if(head->data==todelete)
{
p=head;
head=head->next;
free(p);
}
else
{
pre=head;
p=head->next;
while(p!=NULL&&p->data!=todelete)
{
pre=p;
p=p->next;
}
if(p!=NULL)
{
pre->next=p->next;
free(p);
}else
{
printf("Not Found\n");
}
}
return head;
}
  • 广义表

  • 多重链表

2.2 堆栈

例1 计算机如何进行表达式求值

考虑运算符与运算符号及其相应的优先级不同

平时我们运用的都是中缀表达式

现在我们来看后缀表达式的求值策略:从左向右扫描,逐个处理运算数和运算符号

例 6 2 / 3 - 4 2 * + = ? (8)

堆栈的抽象数据类型描述

栈的顺序存储实现

栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdio.h>
#include <stdlib.h>
#define Max 100000
typedef struct SNode * Stack;
struct SNode{
int Data[Max];
int Top;
};
Stack CreateStack()
{
Stack head=(Stack)malloc(sizeof(struct SNode));
head->Top=-1;
return head;
}
void Push(Stack head,int data)
{
if(head->Top==Max-1)
{
printf("堆栈已满\n");
return ;
}else{
head->Data[++(head->Top)]=data;
}
}
int Pop(Stack head)
{
if(head->Top==-1)
{
printf("堆栈为空\n");
return NULL;
}else{
return head->Data[(head->Top)--];
}
}
int main()
{
Stack head=CreateStack();
Push(head,1);
Push(head,2);
printf("%d\n",Pop(head));
printf("%d\n",Pop(head));
}

例 请用一个数组实现两个堆栈,要求最大利用数组空间.使数组只要有空间入栈操作就可以成功

解:

可以在数组两边Top位置分别向中间靠拢,若Top值相差为一,则说明堆栈已满

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <stdio.h>
#include <stdlib.h>
#define Max 100000
typedef struct SNode * Stack;
struct SNode
{
int Data[Max];
int Top1;
int Top2;
};
Stack CreateStack()
{
Stack head=(Stack)malloc(sizeof(struct SNode));
head->Top1=-1;
head->Top2=Max;
return head;
}
void Push(Stack head,int data,int Tag)
{
if(head->Top1-head->Top2==-1)
{
printf("堆栈已满\n");
return ;
}
if(Tag==1)
{
head->Data[++(head->Top1)]=data;
}
else
{
head->Data[--(head->Top2)]=data;
}
}
int Pop(Stack head,int Tag)
{
if(Tag==1)
{
if(head->Top1==-1)
{
printf("堆栈为空\n");
return NULL;
}
else
{
return head->Data[(head->Top1)--];
}
}else
{
if(head->Top2==-1)
{
printf("堆栈为空\n");
return NULL;
}
else
{
return head->Data[(head->Top2)++];
}
}
}

堆栈的链式存储实现

堆栈的Top只能在链头而不是链尾

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <stdio.h>
#include <stdlib.h>
#define Max 100000
typedef struct SNode * Stack;
struct SNode{
int Data;
Stack next;
};

Stack createStack()
{
Stack head=(Stack)malloc(sizeof(struct SNode));
head->next=NULL;
return head;
}

Stack createNode(int data)
{
Stack Node=(Stack)malloc(sizeof(struct SNode));
Node->Data=data;
Node->next=NULL;
return Node;
}

void PushStack(Stack head,int data)
{
Stack Node=createNode(data);
Node->next=head->next;
head->next=Node;
}

int PopStack(Stack head)
{
if(head->next==NULL)
{
printf("堆栈为空!\n");
return NULL;
}else{
Stack freeNode=head->next;
head->next=freeNode->next;
int data=freeNode->Data;
free(freeNode);
return data;
}

}

int main()
{
Stack head=createStack();
PushStack(head,1);
PushStack(head,2);
printf("%d\n",PopStack(head));
printf("%d\n",PopStack(head,head->next));
}

堆栈应用

中缀表达式求值
  • 基本策略:中缀表达式转换成后缀表达式,然后求值

其他应用:

函数调用及其递归实现

深度优先搜索

回溯算法

2.3 队列

队列:具有一定操作约束的线性表

  • 先进先出(FIFO):一端插入,一端删除

队列的抽象数据类型描述

队列的顺序存储实现

通常由一个一位数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素位置的变量rear组成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <stdio.h>
#include <stdlib.h>
#define Max 100000
typedef int Position;
typedef struct QNode *Queue;
struct QNode
{
int * Data;
Position Front,Rear;
int MaxSize;
};

Queue createQueue(int MaxSize)
{
Queue q=(Queue)malloc(sizeof(struct QNode));
q->Data=(int *)malloc(MaxSize * sizeof(int));
q->Front=q->Rear=0;
q->MaxSize=MaxSize;
return q;
}

int IsFull(Queue q)
{
return ((q->Rear+1)%q->MaxSize==q->Front)?1:0;
}

int IsEmpty(Queue q)
{
return (q->Front == q->Rear)?1:0;
}

void AddQueue(Queue Q,int data)
{
if(IsFull(Q))
{
printf("队列已满!\n");
return ;
}
else
{
Q->Rear=(Q->Rear+1)%Q->MaxSize;
Q->Data[Q->Rear]=data;
}
}

int DeleteQueue(Queue Q)
{
if(IsEmpty(Q))
{
printf("队列为空!\n");
return NULL;
}
else
{
Q->Front = (Q->Front+1)%Q->MaxSize;
return Q->Data[Q->Front];
}
}

队列的链式存储实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <stdio.h>
#include <stdlib.h>
#define Max 100000
typedef struct Node * PtrToNode;
struct Node{
int data;
PtrToNode Next;
};
typedef PtrToNode Position;
struct QNode{
Position Front,Rear;
};
typedef struct QNode * Queue;

Queue createQueue()
{
Queue q=(Queue)malloc(sizeof(struct QNode));
PtrToNode node=(PtrToNode)malloc(sizeof(struct Node));
node->Next=NULL;
q->Front=node;
q->Rear=node;
return q;
}

int IsEmpty(Queue q)
{
return (q->Front==NULL)?1:0;
}


void AddNode(Queue q,int data)
{
PtrToNode node=(PtrToNode)malloc(sizeof(struct Node));
node->data=data;
node->Next=NULL;
q->Rear->Next=node;
q->Rear=node;
}

int DeleteNode(Queue q)
{
if(IsEmpty(q))
{
printf("队列为空\n");
return NULL;
}
PtrToNode Froncell=q->Front;
if(q->Front == q->Rear)
{
q->Front=NULL;
q->Rear=NULL;
}
else
{
q->Front=q->Front->Next;
}
int data=Froncell->data;
free(Froncell);
return data;
}
void PrintQueue(Queue e)
{
PtrToNode p=e->Front->Next;
while(p)
{
printf("%d\n",p->data);
p=p->Next;
}
}

2.4 应用实例:多项式加法运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <stdio.h>
#include <stdlib.h>
#define Max 100000
struct PolyNode{
int coef;
int expon;
struct PolyNode* link;
};
typedef struct PolyNode * Polynomial;

Polynomial PolyAdd(Polynomial P1,Polynomial P2)
{
Polynomial front,rear,temp;
int sum;
rear=(Polynomial)malloc(sizeof(struct PolyNode));
front=rear;
while(P1&&P2)
{
switch(Compare(P1->expon,P2->expon)){
case 1:
Attach(P1->coef,P1->expon,&rear);
P1=P1->link;
break;
case -1:
Attach(P2->coef,P2->expon,&rear);
P2=P2->link;
break;
case 0:
sum=P1->coef+P2->coef;
if(sum)Attach(sum,P1->expon,&rear);
P1=P1->link;
P2=P2->link;
break;
}
}
for(;P1;P1=P1->link){Attach(P1->coef,P1->expon,&rear);}
for(;P2;P2=P2->link){Attach(P2->coef,P2->expon,&rear);}
rear->link=NULL;
temp=front;
front=front->link;
free(temp);
return front;

}

int Compare(int a,int b)
{
if(a>b)return 1;
else if(a<b)return -1;
else return 0;
}

void Attach(int coef,int expon,Polynomial * pRear)
{
Polynomial p;
p=(Polynomial)malloc(sizeof(struct PolyNode));
p->coef=coef;
p->expon=expon;
p->link=NULL;
(*pRear)->link=p;
*pRear=p;
}
CATALOG
  1. 1. 第二讲 线性结构
    1. 1.1. 2.1 线性表及其表示
    2. 1.2. 2.2 堆栈
      1. 1.2.1. 堆栈的抽象数据类型描述
      2. 1.2.2. 栈的顺序存储实现
      3. 1.2.3. 堆栈的链式存储实现
      4. 1.2.4. 堆栈应用
        1. 1.2.4.1. 中缀表达式求值
    3. 1.3. 2.3 队列
      1. 1.3.1. 队列的抽象数据类型描述
      2. 1.3.2. 队列的顺序存储实现
      3. 1.3.3. 队列的链式存储实现
    4. 1.4. 2.4 应用实例:多项式加法运算