数据结构之线性结构讲义.

线性结构数据结构什么是数据结构？数据结构(DataStructure),用于描述计算机中数据的存储、组织形式。合理的数据结构可以给程序带来更高的存储和运行效率。常用的数据结构有哪些？1.线性结构2.树型结构3.图型结构栈、队列、链表栈栈(stack)是一种特殊的线性结构，它只能在一端进行插入和删除操作。能插入和删除的一端栈顶（top），另一端称为栈底(bottom)。不含任何元素的栈称为空栈。只允许在栈顶进行插入和删除，所以栈的操作是按“后进先出”（LastInFirstOut）的原则进行的。栈底(bottom)栈顶(top)栈的实例1：汉诺塔栈的实例2：弹夹栈顶(top)装弹、出弹285top（栈顶）用数组模拟栈的“后进先出”加入一个数7取出栈顶元素再取出栈顶元素9bottom（栈底,值为0）数组（栈）123456下标栈为空的条件是：top==bottomtop始终指向栈顶一般情况下，top的值就表示了栈中的元素个数//插入（压栈）voidpush(charx){if(top==maxn)coutfull;else{top++;stack[top]=x;}}//删除(弹栈)voidpop(){if(top==0)coutempty;else{coutstack[top];top--;}}constintmaxn=1000charstack[maxn+1];inttop=0;4321使用栈进行算术表达式求值表达式：3×(5–2)+7@数字运算符3×(5–23+975–2=33×3=97+9=16结果便是16！16栈的实例2：混合运算考题（初赛）若S是一个大小为4的栈，若元素1，2，3，4，5，6，7按顺序依次进栈，则这7个元素的出栈顺序可能为（）A.1,2,3,4,5,6,7B.1,4,3,5,7,2,6C.1,3,2,4,7,5,6D.2,3,7,6,5,4,1栈的实例3：火车调度(NKOJ1914)某城市有一个火车站，如下图所示，现有n（n=10000）节火车车厢，顺序编号为1,2,3,...,n，按编号连续依次从A方向的铁轨驶入车站，从B方向铁轨驶出。一旦车厢进入车站就不能再回到A方向的铁轨上；在车站的门口有工人可以将车厢拖出车站，工人一次只能拖一节车厢，并且只能将车厢拖入B方向的铁轨。一旦车厢出了车站就不能再回到车站。车站一开始为空，最多能停放10000节车厢。为了方便装货，调度员需要将车厢从新排列，问能否将车厢编号排列成A1,A2,......,An。也就是使车厢从B方向驶出的编号是A1,A2,......,An。如果能输出yes，否则输出no。输入格式：第一行，一个整数n第二行，n个用空格间隔的整数，表示出站时车厢编号要排列成的顺序A1,A2,......,An输出格式：一行，一个单词yes或者no样例输入1：532541样例输出1:yes样例输入2：531542样例输出2:no车站AB驶入驶出//将题目要求的出站序列读入a数组，然后通过栈从左到右依次去匹配a数组#includeiostream#includecstdiousingnamespacestd;ints[10001],a[10001],n,i,j,top=0;//s数组用于模拟栈intmain(){scanf(%d,&n);for(i=1;i=n;i++)scanf(%d,&a[i]);i=j=1;while(i=n)//依次讨论火车进站的编号1到n{//将第i辆车入站(栈)，把编号存入栈顶top++;s[top]=i;//while讨论如果栈顶的编号与当前要匹配的a的编号相同，则表示可以出站while((s[top]==a[j])&&(top0)){top--;j++;}i++;//讨论下一辆车}//如果栈不为空，表示有编号无法匹配if(top==0)printf(yes\n);elseprintf(no\n);return0;}队列队列（queue）是另一种特殊的线性表，它的特点是删除操作在一头进行，插入操作在另一头进行。允许删除的一端称为队首（head）,允许插入的一端称为队尾(tail)。不含任何元素的队称为空队。队列的修改是按先进先出(FirstInFirstOut)的原则进行队首（head）队尾（tail）用数组模拟队列的“先进先出”C12345678数组（队列）数组下标head(队首)tail(队尾)FXM1.插入数据：2.插入数据：3.插入数据：4.删除数据4.删除数据5.插入数据：当head==tail时表示队列为空head指向队首tail指向下一个空位在队首进行删除在队尾进行插入队列的代码实现#definemaxn101charqueue[maxn];inthead,tail;//入队（插入元素）voidinsert(charx){if(tailmaxn)coutfull;else{queue[tail]=x;tail++;}}//出队(删除元素)voiddel(){if(tail==head)coutempty;else{coutqueue[head];head++;}}试题（初赛）设栈S和队列Q初始状态为空,元素e1,e2,e3,e4,e5,e6依次通过栈S,一个元素出栈后即进入队列Q,若出队的顺序为e2,e4,e3,e6,e5,e1,则栈S的容量至少应该为().A)2B)3C)4D)5例：纸牌游戏（NKOJ1917）桌上有一叠纸牌，共n张牌。从位于顶端的纸牌开始从上往下依次编号为1到n。现在反复进行以下操作：把位于顶端的牌扔到，然后把新的位于顶端的牌放到整叠牌的底部。直到只剩下一张牌。输入n(=100)，输出每次扔掉的牌的编号以及最后剩下的牌的编号。样例输入：7样例输出：1357426intq[201],head,tail,i,n;intmain(){cinn;for(i=1;i=n;i++)q[i]=i;//队列赋初值head=1;//队首指针指向位于顶端的牌的位置tail=n+1;//对尾指针指向下一个空位while(headtail)//如果队列不为空{printf(%d,q[head]);//输出队首，即扔到最顶端的牌head++//队首指针指向新的位于顶端的牌q[tail]=q[head];//将位于最顶端的牌移到队尾tail++;//对尾指针指向下一个可用空位head++;//队首指针指向新的位于顶端的牌}return0;}链表甲乙丙丁戊左：无右：甲左：丙右：戊左：甲右：乙左：戊右：丁左：乙右：无链表（list），由多个结点连接而成的链状结构。每个结点包含两部分，数值和存放结点间的相互关系右图中，每个人看做一个节点，数值就是每个人自己的名字。同时记录下左边是谁，右边是谁，这就是节点间的关系。061423152380链表（list），由多个结点连接而成的链状结构。每个结点包含两部分，数值和存放结点间的相互关系。编号1编号2编号3编号4双向链表：121133152220编号1编号2编号3编号4单向链表：左A右DBC在1和2间插入4号点D1.让4的左手牵2的左手牵的对象list[4].left=list[2].left;2.让4的右手牵1的右手牵的对象list[4].right=list[1].right3.让1的右手放开2，然后牵4list[1].right=4;4.让2的左手放开1，然后牵4list[2].left=4;删除B1.让4的右手牵2的右手牵的对象list[4].right=list[2].right;2.让3的左手牵2的左手牵的对象list[3].left=list[2].left;3.让2的右手放开list[2].right=0;4.让2的左手放开list[2].left=0;structnode{charname;intleft,right;};nodelist[10];123list[1].right=2;list[1].left=0;list[2].right=3;list[2].left=1;list[3].right=0;list[3].left=2;4head链表的代码实现nodelist[100];//把编号x的元素插到p号点之后voidinsert(intp,intx){list[x].right=list[p].right;list[x].left=p;list[list[p].right].left=x;list[p].right=x;}//删除编号为x的结点voiddel(intx){intp,q;if(head==x)head=list[x].left;p=list[x].left;q=list[x].right;list[p].right=list[x].right;list[q].left=list[x].left;list[x].left=0;list[x].right=0;}//查找链表中的名为helang的结点的编号voidsearchList(strings){intp;p=head;while((p!=0)&&(list[p].name!=helang))p=list[p].right;if(list[p].name==helang)coutp;elsecoutnotfound;}structnode{charname;intleft,right;};17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：25个基督教徒和25个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：50个人围坐成一圆圈，从第一个人开始顺时针依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余25个人为止。问怎样排座位，才能使每次投入大海的都是非教徒。structpeople{//right为上一个人的编号intleft,right;//left为下一个人的编号booldead;//如果dead为true表示要被扔下海};peopleren[51];inti,n,p,x,y;intmain(){for(i=1;i=50;i++){ren[i].left=i+1;ren[i].right=i-1;ren[i].dead=false;}ren[1].right=50;ren[50].left=1;n=50;p=50;while(n25){for(i=1;i=9;i++)p=ren[p].left;x=ren[p].right;y=ren[p].left;ren[x].left=y;ren[y].right=x;ren[p].dead=true;n--;}for(i=1;i=50;i++)if(ren[i].dead==false)couti;coutendl;return0;}123要删除2号节点leftleftrightrightrightleftxy课后练习：1085网页浏览NKOJ1085网页浏览器都包含有前进和后退功能，以此来快速打开之前你访问过的网页。你的任务就是实现这个功能。实现此功能的常用方法是通过forword和back两个栈来保存前进和后退时要打开的网页。下列命令是你需要实现的：BACK:把当前显示的网页压入到forword栈中。然后把back栈栈顶的网页弹出作为当前显示的网页。如果back栈为空，那么这条命令就不执行。FORWARD:把当前显示的网页压入到back栈中。然后把forward栈栈顶的网页弹出作为当前显示的网页。如果forward栈为空，那么这条命令就不执行。VISIT:把当前显示的网页压入到back栈中。然后浏览器显示用户新输入的网址对应的网页。清空forward栈QUIT:关闭浏览器假设只要浏览器一打开就会自动打开网页输入格式：包含若干条命令，这些命令由BACK,FORWARD,VISIT和QUIT构成。每条命令占一行，长度不超过70。命令的总条数不超过100。一旦出现Q