计算机软件基础课件：线性数据结构

线性数据结构《计算机软件基础》本章重点难点本章重点：线性表的特点；顺序表和链表上的基本操作；栈、队列的概念及基本操作；栈的应用；特殊矩阵压缩存储时元素的位置。本章难点：单链表上的操作；栈的应用。01.线性表02.栈03.队列04.特殊矩阵的压缩存储主要内容01线性表1.线性表的概念线性表是一种简单且常用的数据结构。线性表是由n（n≥0）个相同类型的数据元素a1、a2、a3、…、an组成的有限序列。n=0，为空表。对于非空的线性表，每个数据元素都有一个确定的位置，有且仅有一个开始数据元素和一个终端数据元素，其余数据元素有且仅有唯一的一个直接前驱和唯一的一个直接后继。例如： inta[5];

定义a为一个整型数组，可以用来存储线性表，其长度为5，每个数据元素都是整型。2.线性表的顺序存储结构1）顺序表用一组地址连续的存储空间依次（逻辑顺序）存放线性表中的各个数据元素

线性表中逻辑上相邻的数据结点在物理位置上也相邻。2）顺序表上的基本操作可以用一维数组来实现线性表的顺序存储。方式：静态方式：存储数组的大小和空间事先已经固定分配动态方式：是存储数组的空间在程序执行过程中通过动态存储分配语句来分配顺序表的静态存储表示如下：#defineM100/*顺序表最大长度为M*/typedefintElemType; /*此处以整型元素为例*/typedefstruct{ElemTypedata[M];intlength; /*length代表线性表的当前长度*/}SqList; /*定义SqList线性表类型*/①查找操作线性表的查找是在表中查找与给定值x相等的数据元素的位置。例8-1在长度为n的线性表L中顺序查找内容为x的数据元素，找到则返回下标值，没找到则返回-1。然后，计算成功的平均查找次数及时间复杂度T(n)。/*在线性表L中顺序查找内容为x的数据元素*/intsearch_Sq(SqListL,intx){ inti;for(i=0;i<L.length;i++)if(L.data[i]==x)returni;/*返回找到第一个值相等元素的下标，从0开始*/return-1;/*没有找到返回-1*/}

②插入操作线性表的插入操作是指在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素，使长度为n的线性表变成长度为n+1的线性表。

intinsert_Sq(SqList*L,inti,intx){intj;if(i<0||i>L->length||L->length==M)return0;/*插入位置非法或线性表已满，插入失败*/for(j=L->length-1;j>=i;j--)L->data[j+1]=L->data[j];/*将第i个位置及之后的元素都向后移动一位*/L->data[i]=x;/*将x插入到第i个位置*/L->length++;/*线性表长度加1*/return1;/*插入成功*/}

③删除操作

intdelete_Sq(SqList*L,inti){intj; if(i<0||i>=L->length)return0;/*删除位置非法，删除失败*/for(j=i;j<L->length-1;j++)L->data[j]=L->data[j+1];/*将第i+1个位置及之后的元素都向前移动一位*/L->length--;/*线性表长度减1*/return1;/*删除成功*/}

3.线性表的链式存储结构用一组任意的存储单元存储线性表的数据元素，这些存储单元可以是连续的，也可以是不连续的。数据元素的存储映像（结点）：数据域+指针域1）单链表（线性链表）利用指针将链表各结点按其逻辑顺序依次链接起来。①求表长表长是单链表中数据元素结点的个数。例8-4求带头结点单链表的表长。intgetlen_SL(SLinkedList*head)/*head是指向单链表的头指针*/{SLinkedList*p;intn=0;/*结点个数用n记录，置初值为0*/p=head; /*p指向头结点*/while(p->next!=NULL)/*p不是最后一个结点则进行循环*/{p=p->next;/*p指针前进一个结点*/n++;/*结点个数加1*/}returnn; /*返回链表表长n*/}

②查找操作例8-5在单链表中查找元素值为x的结点，若找到，返回该点地址；否则返回NULL。SLinkedList*search_SL(SLinkedList*head,ElemTypex){SLinkedList*p;p=head->next;/*置初态，p指向单链表的第一个数据元素结点*/while(p!=NULL&&p->data!=x)/*当p尚未指向空，且p的data值不是x时*/ p=p->next;/*p指针后移*/if(p->data==x) returnp;/*找到x则返回指向该结点的指针p*/else returnNULL;/*没找到返回NULL*/}

③插入操作例8-6在指针p所指的单链表结点后面插入元素值为x的结点。

创建被插入结点ss=(SLinkedList*)malloc(sizeof(SLinkedList));s->data=x;①让s的next指向p的下一个结点，即s->next=p->next；②让p的next指向s结点，即p->next=s。④删除操作

首先，将p的下一个结点地址保存到q中，即令q=p->next；其次，从链表中删除结点q，p的next指向q的下一个结点，即令p->next=q->next；最后，回收被删除的q所指结点的空间，即free(q)。⑤单链表的建立头插法。头插法的特点是每次总是将新结点插在表头结点head的后面。尾插法。尾插法的特点是每次总是将新结点插在当前链表的尾部。例8-7依次输入一串字符"abc"，以"*"为结束标记。例8-8依次输入一串字符“abc”，以“*”作为结束标记。2）循环单链表循环链表：将链表中最后一个结点的指针指向头结点，整个链表形成一个环。循环单链表的操作和单链表的操作基本一致，差别仅在于算法中的循环条件不是p或p->next是否为空，而是它们是否等于头指针。

例8-9一个带头结点循环单链表，假设它只有尾指针r，且最少具有两个数据域有值的结点，试写出删除r的前一个结点操作的算法。首先，找出r的前前一个结点p；然后，把p的下一个结点（即r的前一个结点，被删除结点）地址保存到q中；最后，从链表中删除q结点，并回收q结点空间。时间复杂度：T(n)=O(n)3）双向链表prior称为左链域，存放直接前驱（左边）结点的地址。next称为右链域，存放直接后继（右边）结点的地址。data称为数据域，存放该结点的信息内容。插入操作删除操作时间性能顺序存储结构：对于随机访问操作（根据数组下标查找元素），时间复杂度为O(1)。对于插入和删除操作，需要移动后续元素来保持顺序，平均情况下的时间复杂度为O(n)。链式存储结构：对于插入和删除操作，时间复杂度为O(1)，仅需调整指针即可。对于随机访问操作，链式存储结构需要遍历结点来查找特定位置的元素，时间复杂度为O(n)。空间性能顺序存储结构：顺序存储结构的空间利用率高。链式存储结构：需要额外的空间来存储指针，因此，链式存储结构的空间利用率相对较低。

需要根据具体的应用场景和需求来选择合适的存储结构，权衡时间和空间性能的优劣。4）顺序和链式存储结构的比较02栈栈:特殊线性表，一端固定，只允许在另一端插入和删除的线性表。又称堆栈。pushpoptopbottom栈底、栈顶、入栈、出栈、栈空、栈满……与一般线性表的相同和不同？特性：“先进后出(FILO:FirstInLastOut)”或“后进先出(LIFO-LastInFirstOut)”

元素关系操作特殊在操作：操作受限制！1.栈的概念2.栈的顺序存储结构顺序栈类型定义如下：#defineM100/*栈的容量*/typedefcharElemType;typedefstructSnode{ElemTypedata[M];inttop;/*栈顶指针*/}SeqStack;1）顺序栈的类型定义2）顺序栈的基本操作①进栈：在向s栈中加入值为x的新元素时，首先判断栈是否已满；若满，则进行上溢处理，返回；不满则top加1，并将x放入data数组的top位置。voidpush(SeqStack*s,ElemTypex){if(s->top==M-1){printf("栈满\n");return;}s->top++;s->data[s->top]=x;}特点：简单、方便，但易产生溢出。■上溢(Overflow):栈已经满，又要压入元素；■下溢(Underflow)：栈已经空，还要弹出元素；②出栈：首先判断栈是否为空；若栈为空，则进行下溢处理（返回一个特殊错误标志'\0'）；若不空，返回栈顶元素，同时将栈顶指针top减1。出栈操作算法描述如下：ElemTypepop(SeqStack*s){ElemTypeitem;if(s->top==-1){printf("栈空\n");return'\0';}item=s->data[s->top];s->top--;returnitem;}3.栈的链式存储结构1）链栈的类型定义链栈类型定义如下：typedefcharElemType;typedefstructLsnode{ElemTypedata;structLsnode*next;}LinkStack;2）链栈的基本操作①进栈：向链栈的栈顶插入数据元素x。LinkStack*push(LinkStack*Ls,ElemTypex){LinkStack*s=(LinkStack*)malloc(sizeof(LinkStack));if(s==NULL){printf("内存分配失败.\n");returnLs;}s->data=x;s->next=Ls;Ls=s;returnLs;}②出栈：链栈的出栈操作即删除栈顶元素。算法实现如下：LinkStack*pop(LinkStack*Ls,ElemType*x){if(Ls==NULL){printf("栈空.\n");returnLs;}*x=top->data;LinkStack*temp=Ls;Ls=Ls->next;free(temp);returnLs;}4.栈的应用1）出栈顺序判断例8-10

若将a、b和c三个字符元素依次进栈，试问可能有多少种出栈顺序，它们分别是什么?三个字符元素的全排列有六种：分别是abc、acb、bac、bca、cab、cba。下面逐一进行分析：要得到abc出栈顺序、其进、出栈过程为：a进→a出→b进→b出→c进→c出。acb的进、出栈过程为：a进→a出→b进→c进→c出→b出。bac的进、出栈过程为：a进→b进→b出→a出→c进→c出。bca的进、出栈过程为：a进→b进→b出→c进→c出→a出。要想得到出栈顺序cba，也就是要想c先出来，abc依次都得进栈。其过程为：a进→b进→c进；最后的出栈顺序只能为cba，而不可能得到cab，因为a要出来，b必须先出来。本题结果是有五种出栈顺序，分别为abc、acb、bac、bca、cba。[问题]如果将A、B、C、D四个字符按顺序压入堆栈，出栈顺序任意，那么是不是A、B、C、D的所有排列都可能是出栈的序列？可以产生CABD这样的序列吗？2）数值转换十进制数N和其他d进制数的转换。

NN/8N%8134816841682102125202while(N){ push(&stack,N%8); N=N/8;}while(!isEmpty(&stack)){ e=pop(&stack); printf("%d",e);}3）表达式求值(中缀)例8-12试写出表达式9+4*6/8-5求值时栈的变化过程。4）逆置操作例8-13

利用栈逆置单链表。基本思路是将单链表元素从头依次进栈，然后栈内元素再依次出栈从头放入单链表中。voidtransLink(SLinkedList*head){SeqStackstack;SLinkedList*p;initStack(&stack);/*创建一个空栈stack*/p=head->next;/*p指向单链表的第一个数据结点*/while(p!=NULL)/*链表中元素尚未全部进栈时*/{push(&stack,p->data);/*将p指向结点的数据进栈*/p=p->next; /*p指针下移*/}p=head->next;/*再将p指向单链表的第一个数据结点*/while(!isEmpty(&stack))/*若栈非空*/{p->data=pop(&stack);/*栈顶元素出栈放入p所指结点数据域*/p=p->next;/*p指针下移*/}}03队列1.队列的概念只允许在一端插入，在另一端删除的线性表。队首、队尾、入队、出队、队空、队满……与一般线性表的相同和不同？特性：“先进先出(FIFO)”或“后进后出(LILO)”元素关系操作rearfront特殊在操作：操作受限制！2.队列的顺序存储结构1）顺序队列的类型定义#defineM100/*假设队列空间最多容纳100个元素，即队列的容量*/typedefcharElemType;typedefstructqnode{ElemTypedata[M];intfront;intrear;}seqQueue;2）顺序队列的基本操作①入队voidenqueue(seqQueue*queue,ElemTypex){if(queue->rear==M-1){printf("队列已满，无法插入元素\n");return;}queue->rear++;queue->data[queue->rear]=x;}②出队ElemTypedequeue(seqQueue*q