数据结构c语言版答案（C语言数据结构求解）

本文目录

• C语言数据结构求解
• 急需数据结构C语言版（清华大学出版社）的期末考试试题及答案
• 数据结构c语言版问题
• 数据结构（C语言版），求高手解决
• 求数据结构（C语言版 ）的几道题目的答案，希望各位大侠说详细点再此谢过了可发邮箱；379333655@qq.com
• 数据结构 （c语言版）胡学纲 课后习题 答案谢谢了，大神帮忙啊
• 数据结构（c语言版）题目求答案
• 清华大学严蔚敏数据结构题集完整答案（c语言版）

C语言数据结构求解

方法很多，可以在插入数据后再对线性表进行删改，也可以在插入前进行处理。

我这里代码是在插入前处理。

（注释掉的函数int getPNUM(struct Sqlist *st,int n);是我预留的，题2如果你想改成插入后，再对线性表素数进行查找，可以用这个函数。否则可以删除）。

#include 《stdio.h》

#include 《stdlib.h》

#include 《time.h》

#define LIST_INIT_SIZE 800

struct Sqlist{

    int *elem;

    int length;

    int listsize;

};

int insert2List(struct Sqlist *st,int num,int inx);//向线性表第inx个元素的位置插入一个元素。成功返回1,失败返回0

int findNum(struct Sqlist *st,int num);//在线性表中查找指定数字，存在返回1，不存在返回0

//int getPNUM(struct Sqlist *st,int n);//查找素数，返回第几n个素数的下标。未找到返回-1

void showList(struct Sqlist *st);//打印线性表

void clearList(struct Sqlist *st);//清空线性表

int main()

{

    int i,k,nums,n,num,cnt,flag;

    struct Sqlist st={nums,0,LIST_INIT_SIZE};

    srand(time(NULL));

//--------------题1-----------------------------------------------------------------------

    n=100;

    k=1;

    printf("1、随机生成100个【100,200】之间的随机数，去除重复并保存到线性表\n");

    while(n--)

    {

        num=rand()%101+100;

        printf("--%3d产生随机数%d\n",k++,num);

        if(findNum(&st,num))

            printf("该数字已在线性表中存在，重复去除\n");

        else

        {

            if(insert2List(&st,num,st.length+1))

                printf("该随机值已保存到线性表尾部\n");

            else{

                printf("异常!插入失败!\n");

                return 1;

            }

        }

    }

    showList(&st);

    clearList(&st);

//-------------题2----------------------------------------------------------------

    n=20;

    cnt=0;

    k=1;

    printf("1、随机生成20个【1,200】之间的随机数，在第一个素数后插入1个0，第二个素数后插入2个0，以此类推，最后输出所有元素\n");

    while(n--)

    {

        num=rand()%200+1;

        printf("--%3d产生随机数%d\n",k++,num);

        flag=1;

        for(i=2;i《num;i++)

            if(num%i==0)

            {

                flag=0;

                break;

            }

        if(flag)

        {

            cnt++;

            printf("该随机值是一个素数，在其尾部插入%d个0\n",cnt);

            for(i=0;i《cnt;i++)

                num*=10;

            printf("该随机值变更为%d\n",num);

        }

        if(insert2List(&st,num,st.length+1))

            printf("该随机值已保存到线性表尾部\n");

        else{

            printf("异常!插入失败!\n");

            return 1;

        }

    }

    showList(&st);

    return 0;

}

void clearList(struct Sqlist *st)//清空线性表

{

    st-》length=0;

    printf("线性表数据已清除\n");

}

void showList(struct Sqlist *st)//打印线性表

{

    int i;

    printf("当前线性表的数据为:\n");

    for(i=0;i《st-》length;i++)

        printf("%d ",st-》elem);

    printf("\n");

}

int findNum(struct Sqlist *st,int num)//在线性表中查找指定数字，存在返回1，不存在返回0

{

    int *p=st-》elem;

    while(p《=&st-》elem)

        if(*p++==num)

            return 1;

    return 0;

}

/*

int getPNUM(struct Sqlist *st,int n)//查找素数，返回第几n个素数的下标。未找到返回-1

{

    int i,j,flag,cnt=0;

    for(i=0;i《st-》length;i++)

    {

        flag=1;

        for(j=2;j《st-》elem;j++)

            if(st-》elem%j==0)

            {

                flag=0;

                break;

            }

        if(flag)

            cnt++;

        if(cnt==n)

            return i;

    }

    return -1;

}

*/

int insert2List(struct Sqlist *st,int num,int inx)//向线性表第inx个元素的位置插入一个元素。成功返回1,失败返回0

{

    int i;

    if(st-》length==st-》listsize)

    {

        printf("线性表已满，插入失败！\n");

        return 0;

    }

    if(inx《1 && inx》st-》length+1)

    {

        printf("插入位置无效！线性表当前数据长度为%d，插入位置必须大于1且不能大于%d！\n",st-》length,st-》length+1);

        return 0;

    }

    for(i=st-》length;i》=inx;i--)

        st-》elem;

    st-》elem=num;

    st-》length++;

    return 1;

}

急需数据结构C语言版（清华大学出版社）的期末考试试题及答案

《数据结构》期末考试试卷（ A ）一、 选择题（每小题2分，共24分）1．计算机识别、存储和加工处理的对象被统称为( A )A.数据 B.数据元素C.数据结构 D.数据类型2．栈和队列都是（ A ）A．限制存取位置的线性结构 B．顺序存储的线性结构C．链式存储的线性结构 D．限制存取位置的非线性结构 3．链栈与顺序栈相比，比较明显的优点是( D )A.插入操作更加方便 B.删除操作更加方便C.不会出现下溢的情况 D.不会出现上溢的情况4．采用两类不同存储结构的字符串可分别简称为( B )A.主串和子串 B.顺序串和链串C.目标串和模式串 D.变量串和常量串5． 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是：BA. 110 B .108C. 100 D. 120 6．串是一种特殊的线性表，其特殊性体现在：BA.可以顺序存储 B .数据元素是一个字符C. 可以链接存储 D. 数据元素可以是多个字符7．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为： CA. 2h B .2h-1C. 2h+1 D. h+1软件开发网 8．树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把 由树转化得到的二叉树叫做这棵树对应的二叉树。下列结论哪个正确？ AA. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同B .树的后根遍历序列与其对应的二叉树的后序遍历序列相同C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D. 以上都不对9．一个有n个顶点的无向图最多有多少边？CA. n B .n(n-1)C. n(n-1)/2 D. 2n10．在一个图中，所有顶点的度数之和等于所有边数的多少倍?CA. 1/2 B .1C. 2 D. 4 11．当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（ A ）A．左子树的叶子结点 B．左子树的分支结点C．右子树的叶子结点 D．右子树的分支结点软件开发网 12．对于哈希函数H(key)=key%13,被称为同义词的关键字是( D )A.35和41 B.23和39C.15和44 D.25和51 二、已知某棵二叉树的前序遍历结果为A,B,D,E,G,C,F,H,I,J，其中中序遍历的结果为D,B,G,E,A,H,F,I,J,C。请画出二叉的具体结构。（注意要写出具体步骤）（10分）原理见课本128页三、有图如下，请写出从顶点c0出发的深度优先及宽度优先遍历的结果。(10分) 深度优先；C0-C1-C3-C4-C5-C2宽度优先：C0-C1-C2-C3-C4-C5四、有图如下，按Kruskal算法求出其最小生成树。要求写出完整的步骤。（10分）原理见课本250页五、给定线性表（12，23，45，66，76，88，93，103，166），试写出在其上进行二分查找关键字值12，93，166的过程。并写出二分查找的算法。（20分）0 1 2 3 4 5 6 7 812 23 45 66 76 88 93 103 166过程：mid=(0+8)/2=4high=3,low=0 mid=1high=0,low=0 mid=0（找到12）high=8,low=5,mid=6（找到93）high=8,low=7,mid=7high=8 low=8 mid=8算法：见课本84页上六、知单链表的结点结构为Data next下列算法对带头结点的单链表L进行简单选择排序，使得L中的元素按值从小到大排列。请在空缺处填入合适的内容，使其成为完整的算法。 (可用文字说明该算法的基本思想及执行的过程，10分)void SelectSort(LinkedList L){ LinkedList p,q,min; DataType rcd; p= (1) ; while(p!=NULL) { min=p; q=p-》next; while(q!=NULL){ if( (2) )min=q; q=q-》next; } if( (3) ){ rcd=p-》data; p-》data=min-》data; min-》data=rcd; } (4) ; }} 本题不会。嘿嘿。。。。七、一个完整的算法应该具有哪几个基本性质？分别简要说明每一性质的含意。(5分) 输入：四个基本性质：1.输入：有零个或多个有外部提供的量作为算法的输入 2：输出：算法产生至少一个量作为输出 3.：确定性：组成算法的每条指令是清晰的，无歧异的。 4.：有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的八、何谓队列的"假溢"现象？如何解决？（5分）队列的假溢现象是指数组实现的顺序队列中，队尾指针已到达数组的下表上界产生上溢而队头指针之前还有若干 空间闲置的现象。解决的办法之一是利用循环队列技术使数组空间的首尾相连。 九、说明并比较文件的各种物理结构。（6分）

数据结构c语言版问题

按列为主序存放于一个连续的存储空间中a，2表示第三列（前面有0,1），前面两列就是20第三列6个，得到20+6=26，开始地址为200,则200+26=226

数据结构（C语言版），求高手解决

1．二叉树是度为2的有序树（ ）【答案】×2．完全二叉树一定存在度为1的结点（ ）【答案】×3．深度为K的二叉树中结点总数≤2k-1（ ）【答案】√4．由一棵二叉树的先序序列和后序序列可以惟一确定它（ ）【答案】×5．完全二叉树中，若一个结点没有左孩子，则它必是树叶（ ）【答案】√6．用二叉链表存储n个结点的二叉树时，结点的2n个指针中有n+1个空指针（ ）【答案】√7．完全二叉树的存储结构通常采用顺序存储结构（ ）【答案】√8．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近（ ）【答案】√9．在中序线索二叉树中，每一非空的线索均指向其祖先结点（ ）【答案】√【解析】在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点（该结点的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点（该结点的前驱指针指向祖先）。10．二叉树中序线索化后，不存在空指针域（ ）【答案】×

求数据结构（C语言版 ）的几道题目的答案，希望各位大侠说详细点再此谢过了可发邮箱；379333655@qq.com

冒泡排序法：#include《stdio.h》 void main() { int a={24,70,12,85,106,08},i,k,temp; for(k=0;k《6;k++) {for(i=k+1;i《6;i++) if(a) {temp=a; a; a=temp; } printf(" %d",a); } getch(); }选择排序：#include "stdio.h"#define N 6main(){ int i,j,k,t; int a; printf("请输入六位数:\n"); for(i=0;i《N;i++) scanf("%d",&a); for(i=0;i《N-1;i++) { k=i; for(j=i+1;j《N;j++) if(a) k=j; if(i!=k) { t=a; a; a=t; } } for(i=0;i《N;i++) printf("%d\t",a); printf("\n");}插入排序法：#include "stdio.h"#define N 6main(){ int i,j,k; int a; printf("请输入六位数:\n"); for(i=0;i《N;i++) scanf("%d",&a); for(i=0;i《N;i++) { k=a; j=i-1; while(j》=0&&k《a) { a; j--; } a=k; } for(i=0;i《N;i++) printf("%d\t",a); printf("\n");} shell排序法：#include "stdio.h"#define N 6main(){ int i,j,k,m,flag; int a={24,70,12,85,106,08}; m=N; while(m》1) { m=(m+1)/2; do { flag=0; for(i=0;i《N-m;i++) { j=i+m; if(a) { k=a=k;flag=1; } } }while(flag); } for(i=0;i《N;i++) printf("%d ",a); printf("\n");}

数据结构 （c语言版）胡学纲 课后习题 答案谢谢了，大神帮忙啊

数据结构课程第一章部分习题解答 第一章 绪论 1-4．什么是抽象数据类型？试用C++的类声明定义“复数”的抽象数据类型。要求 (1) 在复数内部用浮点数定义它的实部和虚部。 (2) 实现3个构造函数：缺省的构造函数没有参数；第二个构造函数将双精度浮点数赋给复数的实部，虚部置为0；第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。 (3) 定义获取和修改复数的实部和虚部，以及+、-、*、/等运算的成员函数。 (4) 定义重载的流函数来输出一个复数。 【解答】 抽象数据类型通常是指由用户定义，用以表示应用问题的数据模型。抽象数据类型由基本的数据类型构成，并包括一组相关的服务。 //在头文件complex.h中定义的复数类 #ifndef _complex_h_ #define _complex_h_ #include class comlex { public: complex ( ){ Re = Im = 0; } //不带参数的构造函数 complex ( double r ) { Re = r; Im = 0; } //只置实部的构造函数 complex ( double r, double i ) { Re = r; Im = i; } //分别置实部、虚部的构造函数 double getReal ( ) { return Re; } //取复数实部 double getImag ( ) { return Im; } //取复数虚部 void setReal ( double r ) { Re = r; } //修改复数实部 void setImag ( double i ) { Im = i; } //修改复数虚部 complex & operator = ( complex & ob) { Re = ob.Re; Im = ob.Im; } //复数赋值 complex & operator + ( complex & ob ); //重载函数：复数四则运算 complex & operator – ( complex & ob ); complex & operator * ( complex & ob ); complex & operator / ( complex & ob ); friend ostream & operator 《《 ( ostream & os, complex & c ); //友元函数：重载《《 private: double Re, Im; //复数的实部与虚部 }; #endif //复数类complex的相关服务的实现放在C++源文件complex.cpp中 #include #include #include “complex.h” complex & complex :: operator + ( complex & ob ) { //重载函数：复数加法运算。 complex * result = new complex ( Re + ob.Re, Im + ob.Im ); return *result; } complex & complex :: operator – ( complex & ob ) { //重载函数：复数减法运算 complex *result = new complex ( Re – ob.Re, Im – ob.Im ); return * result; } complex & complex :: operator * ( complex & ob ) { //重载函数：复数乘法运算 complex *result = new complex ( Re * ob.Re – Im * ob.Im, Im * ob.Re + Re * ob.Im ); return *result; } complex & complex :: operator / ( complex & ) { //重载函数：复数除法 查看更多答案》》

数据结构（c语言版）题目求答案

3.28void InitCiQueue(CiQueue&Q)//初始化循环链表表示的队列Q{Q=(CiLNode*)malloc(sizeof(CiLNode));Q-》next=Q;}//InitCiQueuevoidEnCiQueue(CiQueue&Q,int x)//把元素x插入循环列表表示的队列Q,Q指向队尾元素，Q-》next指向头结点，Q-》next-》next指向队尾元素{p=(CiLNode*)malloc(sizeof(CiLNode));p-》data=x;p-》next=Q-》next;//直接把p加在Q的后面Q-》next=p;Q=p;//修改尾指针}Status DeCiQueue(CiQueue&Q,int x)//从循环链表表示的队列Q头部删除元素x{if(Q==Q-》next)return INFEASIBLE;//队列已空p=Q-》next-》next;x=p-》data;Q-》next-》next=p-》next;free(p);rturn OK;}//DeCiqueue3.31int Palindrome_Test(){InitStack(S);InitQueue(Q);while((c=getchar())!=’@’){Push(S,c);EnQueue(Q,c);}while(!StackEmpty(S)){pop(S,a);DeQueue(Q,b);if(a!=b)return ERROR;}return OK;}

清华大学严蔚敏数据结构题集完整答案（c语言版）

第一章 绪论 1.16 void print_descending(int x,int y,int z)//按从大到小顺序输出三个数 { scanf("%d,%d,%d",&x,&y,&z); if(x《y) x《-》y; //《-》为表示交换的双目运算符,以下同 if(y《z) y《-》z; if(x《y) x《-》y; //冒泡排序 printf("%d %d %d",x,y,z); }//print_descending 1.17 Status fib(int k,int m,int &f)//求k阶斐波那契序列的第m项的值f { int tempd; if(k《2||m《0) return ERROR; if(m《k-1) f=0; else if (m==k-1) f=1; else { for(i=0;i《=k-2;i++) temp=0; temp=1; //初始化 for(i=k;i《=m;i++) //求出序列第k至第m个元素的值 { sum=0; for(j=i-k;j《i;j++) sum+=temp; temp=sum; } f=temp; } return OK; }//fib 分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). 1.18 typedef struct{ char *sport; enum{male,female} gender; char schoolname; //校名为’A’,’B’,’C’,’D’或’E’ char *result; int score; } resulttype; typedef struct{ int malescore; int femalescore; int totalscore; } scoretype; void summary(resulttype result数组中 { scoretype score ; i=0; while(result.sport!=NULL) { switch(result.schoolname) { case ’A’: score.score; if(result.score; else score.score; break; case ’B’: score .totalscore+=result.score; if(result.score; else score .femalescore+=result.score; break; …… …… …… } i++； } for(i=0;i《5;i++) { printf("School %d:\n",i); printf("Total score of male:%d\n",score.malescore); printf("Total score of female:%d\n",score.femalescore); printf("Total score of all:%d\n\n",score.totalscore); } }//summary 1.19 Status algo119(int a)//求i!*2^i序列的值且不超过maxint { last=1; for(i=1;i《=ARRSIZE;i++) { a=last*2*i; if((a/last)!=(2*i)) reurn OVERFLOW; last=a; return OK; } }//algo119 分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. 1.20 void polyvalue() { float ad; float *p=a; printf("Input number of terms:"); scanf("%d",&n); printf("Input the %d coefficients from a0 to a%d:\n",n,n); for(i=0;i《=n;i++) scanf("%f",p++); printf("Input value of x:"); scanf("%f",&x); p=a;xp=1;sum=0; //xp用于存放x的i次方 for(i=0;i《=n;i++) { sum+=xp*(*p++); xp*=x; } printf("Value is:%f",sum); }//polyvalue第二章 线性表 2.10 Status DeleteK(SqList &a,int i,int k)//删除线性表a中第i个元素起的k个元素{ if(i《1||k《0||i+k-1》a.length) return INFEASIBLE; for(count=1;i+count-1《=a.length-k;count++) //注意循环结束的条件 a.elem; a.length-=k; return OK;}//DeleteK 2.11Status Insert_SqList(SqList &va,int x)//把x插入递增有序表va中{ if(va.length+1》va.listsize) return ERROR; va.length++; for(i=va.length-1;va.elem》x&&i》=0;i--) va.elem; va.elem=x; return OK;}//Insert_SqList 2.12 int ListComp(SqList A,SqList B)//比较字符表A和B,并用返回值表示结果,值为正,表示A》B;值为负,表示A《B;值为零,表示A=B{ for(i=1;A.elem;i++) if(A.elem; return 0;}//ListComp 2.13 LNode* Locate(LinkList L,int x)//链表上的元素查找,返回指针{ for(p=l-》next;p&&p-》data!=x;p=p-》next); return p;}//Locate 2.14 int Length(LinkList L)//求链表的长度{ for(k=0,p=L;p-》next;p=p-》next,k++); return k;}//Length 2.15 void ListConcat(LinkList ha,LinkList hb,LinkList &hc)//把链表hb接在ha后面形成链表hc{ hc=ha;p=ha; while(p-》next) p=p-》next; p-》next=hb;}//ListConcat 2.16 见书后答案. 2.17 Status Insert(LinkList &L,int i,int b)//在无头结点链表L的第i个元素之前插入元素b{ p=L;q=(LinkList*)malloc(sizeof(LNode)); q.data=b; if(i==1) { q.next=p;L=q; //插入在链表头部 } else { while(--i》1) p=p-》next; q-》next=p-》next;p-》next=q; //插入在第i个元素的位置 }}//Insert 2.18 Status Delete(LinkList &L,int i)//在无头结点链表L中删除第i个元素{ if(i==1) L=L-》next; //删除第一个元素 else { p=L; while(--i》1) p=p-》next; p-》next=p-》next-》next; //删除第i个元素 }}//Delete 2.19 Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链表L中值大于mink且小于maxk的所有元素{ p=L; while(p-》next-》data《=mink) p=p-》next; //p是最后一个不大于mink的元素 if(p-》next) //如果还有比mink更大的元素 { q=p-》next; while(q-》data《maxk) q=q-》next; //q是第一个不小于maxk的元素 p-》next=q; }}//Delete_Between 2.20 Status Delete_Equal(Linklist &L)//删除元素递增排列的链表L中所有值相同的元素{ p=L-》next;q=p-》next; //p,q指向相邻两元素 while(p-》next) { if(p-》data!=q-》data) { p=p-》next;q=p-》next; //当相邻两元素不相等时,p,q都向后推一步 } else { while(q-》data==p-》data) { free(q); q=q-》next; } p-》next=q;p=q;q=p-》next; //当相邻元素相等时删除多余元素 }//else }//while}//Delete_Equal 2.21 void reverse(SqList &A)//顺序表的就地逆置{ for(i=1,j=A.length;i《j;i++,j--) A.elem;}//reverse 2.22 void LinkList_reverse(Linklist &L)//链表的就地逆置;为简化算法,假设表长大于2{ p=L-》next;q=p-》next;s=q-》next;p-》next=NULL; while(s-》next) { q-》next=p;p=q; q=s;s=s-》next; //把L的元素逐个插入新表表头 } q-》next=p;s-》next=q;L-》next=s;}//LinkList_reverse分析:本算法的思想是,逐个地把L的当前元素q插入新的链表头部,p为新表表头. 2.23 void merge1(LinkList &A,LinkList &B,LinkList &C)//把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间{ p=A-》next;q=B-》next;C=A; while(p&&q) { s=p-》next;p-》next=q; //将B的元素插入 if(s) { t=q-》next;q-》next=s; //如A非空,将A的元素插入 } p=s;q=t; }//while}//merge1 2.24 void reverse_merge(LinkList &A,LinkList &B,LinkList &C)//把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间{ pa=A-》next;pb=B-》next;pre=NULL; //pa和pb分别指向A,B的当前元素 while(pa||pb) { if(pa-》data《pb-》data||!pb) { pc=pa;q=pa-》next;pa-》next=pre;pa=q; //将A的元素插入新表 } else { pc=pb;q=pb-》next;pb-》next=pre;pb=q; //将B的元素插入新表 } pre=pc; } C=A;A-》next=pc; //构造新表头}//reverse_merge分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩余元素. 2.25 void SqList_Intersect(SqList A,SqList B,SqList &C)//求元素递增排列的线性表A和B的元素的交集并存入C中{ i=1;j=1;k=0; while(A.elem) { if(A.elem) i++; if(A.elem) j++; if(A.elem) { C.elem; //当发现了一个在A,B中都存在的元素, i++;j++; //就添加到C中 } }//while}//SqList_Intersect 2.26 void LinkList_Intersect(LinkList A,LinkList B,LinkList &C)//在链表结构上重做上题{ p=A-》next;q=B-》next; pc=(LNode*)malloc(sizeof(LNode)); while(p&&q) { if(p-》data《q-》data) p=p-》next; else if(p-》data》q-》data) q=q-》next; else { s=(LNode*)malloc(sizeof(LNode)); s-》data=p-》data; pc-》next=s;pc=s; p=p-》next;q=q-》next; } }//while C=pc;}//LinkList_Intersect 2.27 void SqList_Intersect_True(SqList &A,SqList B)//求元素递增排列的线性表A和B的元素的交集并存回A中{ i=1;j=1;k=0; while(A.elem) { if(A.elem) i++; else if(A.elem) j++; else if(A.elem) { A.elem; //当发现了一个在A,B中都存在的元素 i++;j++; //且C中没有,就添加到C中 } }//while while(A.elem=0;}//SqList_Intersect_True 2.28 void LinkList_Intersect_True(LinkList &A,LinkList B)//在链表结构上重做上题{ p=A-》next;q=B-》next;pc=A; while(p&&q) { if(p-》data《q-》data) p=p-》next; else if(p-》data》q-》data) q=q-》next; else if(p-》data!=pc-》data) { pc=pc-》next; pc-》data=p-》data; p=p-》next;q=q-》next; } }//while}//LinkList_Intersect_True 2.29 void SqList_Intersect_Delete(SqList &A,SqList B,SqList C) { i=0;j=0;k=0;m=0; //i指示A中元素原来的位置,m为移动后的位置 while(i《A.length&&j《B.length&& k《C.length) { if(B.elem) j++; else if(B.elem) k++; else { same=B.elem; //找到了相同元素same while(B.elem==same) j++; while(C.elem==same) k++; //j,k后移到新的元素 while(i《A.length&&A.elem《same) A.elem; //需保留的元素移动到新位置 while(i《A.length&&A.elem==same) i++; //跳过相同的元素 } }//while while(i《A.length) A.elem; //A的剩余元素重新存储。 A.length=m; }// SqList_Intersect_Delete分析:先从B和C中找出共有元素,记为same,再在A中从当前位置开始, 凡小于same的元素均保留(存到新的位置),等于same的就跳过,到大于same时就再找下一个same. 2.30 void LinkList_Intersect_Delete(LinkList &A,LinkList B,LinkList C)//在链表结构上重做上题{ p=B-》next;q=C-》next;r=A-next; while(p&&q&&r) { if(p-》data《q-》data) p=p-》next; else if(p-》data》q-》data) q=q-》next; else { u=p-》data; //确定待删除元素u while(r-》next-》data《u) r=r-》next; //确定最后一个小于u的元素指针r if(r-》next-》data==u) { s=r-》next; while(s-》data==u) { t=s;s=s-》next;free(t); //确定第一个大于u的元素指针s }//while r-》next=s; //删除r和s之间的元素 }//if while(p-》data=u) p=p-》next; while(q-》data=u) q=q-》next; }//else }//while}//LinkList_Intersect_Delete 2.31 Status Delete_Pre(CiLNode *s)//删除单循环链表中结点s的直接前驱{ p=s; while(p-》next-》next!=s) p=p-》next; //找到s的前驱的前驱p p-》next=s; return OK;}//Delete_Pre 2.32 Status DuLNode_Pre(DuLinkList &L)//完成双向循环链表结点的pre域{ for(p=L;!p-》next-》pre;p=p-》next) p-》next-》pre=p; return OK;}//DuLNode_Pre 2.33 Status LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiList &C)//把单链表L的元素按类型分为三个循环链表.CiList为带头结点的单循环链表类型.{ s=L-》next; A=(CiList*)malloc(sizeof(CiLNode));p=A; B=(CiList*)malloc(sizeof(CiLNode));q=B; C=(CiList*)malloc(sizeof(CiLNode));r=C; //建立头结点 while(s) { if(isalphabet(s-》data)) { p-》next=s;p=s; } else if(isdigit(s-》data)) { q-》next=s;q=s; } else { r-》next=s;r=s; } }//while p-》next=A;q-》next=B;r-》next=C; //完成循环链表}//LinkList_Divide 2.34 void Print_XorLinkedList(XorLinkedList L)//从左向右输出异或链表的元素值{ p=L.left;pre=NULL; while(p) { printf("%d",p-》data); q=XorP(p-》LRPtr,pre); pre=p;p=q; //任何一个结点的LRPtr域值与其左结点指针进行异或运算即得到其右结点指针 }}//Print_XorLinkedList 2.35 Status Insert_XorLinkedList(XorLinkedList &L,int x,int i)//在异或链表L的第i个元素前插入元素x{ p=L.left;pre=NULL; r=(XorNode*)malloc(sizeof(XorNode)); r-》data=x; if(i==1) //当插入点在最左边的情况 { p-》LRPtr=XorP(p.LRPtr,r); r-》LRPtr=p; L.left=r; return OK; } j=1;q=p-》LRPtr; //当插入点在中间的情况 while(++j《i&&q) { q=XorP(p-》LRPtr,pre); pre=p;p=q; }//while //在p,q两结点之间插入 if(!q) return INFEASIBLE; //i不可以超过表长 p-》LRPtr=XorP(XorP(p-》LRPtr,q),r); q-》LRPtr=XorP(XorP(q-》LRPtr,p),r); r-》LRPtr=XorP(p,q); //修改指针 return OK;}//Insert_XorLinkedList 2.36 Status Delete_XorLinkedList(XorlinkedList &L,int i)//删除异或链表L的第i个元素{ p=L.left;pre=NULL; if(i==1) //删除最左结点的情况 { q=p-》LRPtr; q-》LRPtr=XorP(q-》LRPtr,p); L.left=q;free(p); return OK; } j=1;q=p-》LRPtr; while(++j《i&&q) { q=XorP(p-》LRPtr,pre); pre=p;p=q; }//while //找到待删结点q if(!q) return INFEASIBLE; //i不可以超过表长 if(L.right==q) //q为最右结点的情况 { p-》LRPtr=XorP(p-》LRPtr,q); L.right=p;free(q); return OK; } r=XorP(q-》LRPtr,p); //q为中间结点的情况,此时p,r分别为其左右结点 p-》LRPtr=XorP(XorP(p-》LRPtr,q),r); r-》LRPtr=XorP(XorP(r-》LRPtr,q),p); //修改指针 free(q); return OK;}//Delete_XorLinkedList 2.37 void OEReform(DuLinkedList &L)//按1,3,5,...4,2的顺序重排双向循环链表L中的所有结点{ p=L.next; while(p-》next!=L&&p-》next-》next!=L) { p-》next=p-》next-》next; p=p-》next; } //此时p指向最后一个奇数结点 if(p-》next==L) p-》next=L-》pre-》pre; else p-》next=l-》pre; p=p-》next; //此时p指向最后一个偶数结点 while(p-》pre-》pre!=L) { p-》next=p-》pre-》pre; p=p-》next; } p-》next=L; //按题目要求调整了next链的结构,此时pre链仍为原状 for(p=L;p-》next!=L;p=p-》next) p-》next-》pre=p; L-》pre=p; //调整pre链的结构,同2.32方法}//OEReform分析:next链和pre链的调整只能分开进行.如同时进行调整的话,必须使用堆栈保存偶数结点的指针,否则将会破坏链表结构,造成结点丢失. 2.38 DuLNode * Locate_DuList(DuLinkedList &L,int x)//带freq域的双向循环链表上的查找{ p=L.next; while(p.data!=x&&p!=L) p=p-》next; if(p==L) return NULL; //没找到 p-》freq++;q=p-》pre; while(q-》freq《=p-》freq) q=q-》pre; //查找插入位置 if(q!=p-》pre) { p-》pre-》next=p-》next;p-》next-》pre=p-》pre; q-》next-》pre=p;p-》next=q-》next; q-》next=p;p-》pre=q; //调整位置 } return p;}//Locate_DuList 2.39 float GetValue_SqPoly(SqPoly P,int x0)//求升幂顺序存储的稀疏多项式的值{ PolyTerm *q; xp=1;q=P.data; sum=0;ex=0; while(q-》coef) { while(ex《q-》exp) xp*=x0; sum+=q-》coef*xp; q++; } return sum;}//GetValue_SqPoly 2.40 void Subtract_SqPoly(SqPoly P1,SqPoly P2,SqPoly &P3)//求稀疏多项式P1减P2的差式P3{ PolyTerm *p,*q,*r; Create_SqPoly(P3); //建立空多项式P3 p=P1.data;q=P2.data;r=P3.data; while(p-》coef&&q-》coef) { if(p-》exp《q-》exp) { r-》coef=p-》coef; r-》exp=p-》exp; p++;r++; } else if(p-》exp《q-》exp) { r-》coef=-q-》coef; r-》exp=q-》exp; q++;r++; } else { if((p-》coef-q-》coef)!=0) //只有同次项相减不为零时才需要存入P3中 { r-》coef=p-》coef-q-》coef; r-》exp=p-》exp;r++; }//if p++;q++; }//else }//while while(p-》coef) //处理P1或P2的剩余项 { r-》coef=p-》coef; r-》exp=p-》exp; p++;r++; } while(q-》coef) { r-》coef=-q-》coef; r-》exp=q-》exp; q++;r++; }}//Subtract_SqPoly 2.41 void QiuDao_LinkedPoly(LinkedPoly &L)//对有头结点循环链表结构存储的稀疏多项式L求导{ p=L-》next; if(!p-》data.exp) { L-》next=p-》next;p=p-》next; //跳过常数项 } while(p!=L) { p-》data.coef*=p-》data.exp--;//对每一项求导 p=p-》next; }}//QiuDao_LinkedPoly 2.42 void Divide_LinkedPoly(LinkedPoly &L,&A,&B)//把循环链表存储的稀疏多项式L拆成只含奇次项的A和只含偶次项的B{ p=L-》next; A=(PolyNode*)malloc(sizeof(PolyNode)); B=(PolyNode*)malloc(sizeof(PolyNode)); pa=A;pb=B; while(p!=L) { if(p-》data.exp!=2*(p-》data.exp/2)) { pa-》next=p;pa=p; } else { pb-》next=p;pb=p; } p=p-》next; }//while pa-》next=A;pb-》next=B; }//Divide_LinkedPoly