[数据结构]王道数据结构练习题

数据结构类型定义:
线性表(顺序存储类型描述):
#define MaxSize 50 //定义线性表的最大长度
typedef struct {
    ElemType data[MaxSize]; //顺序表的元素
    int length;             //顺序表的当前长度
} SqList;                   //顺序表的类型定义

线性表(动态存储类型描述)
#define InitSize 100        //表长度的初始定义
typedef struct {            
    ElemType *data;         //指示动态分配数组的指针
    int MaxSize,length;     //数组的最大容量和当前个数
} SeqList;                  //动态分配数组顺序表的类型定义

L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);//初始内存分配

程序设计题
1.从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删元素的值.空出的位置由最后一个
元素填补,若顺序表为空则显示出错信息并退出运行.

//思想:遍历整个顺序表,查找最小值元素并记录其位置,遍历结束后用最后一个元素填补空的原最小值元素位置.
bool Del_MinElem(sqList &L,ElemType &value){
    //删除顺序表L中最小值元素结点,并通过引用型参数value返回其值
    //bool类型:若删除成功,则返回ture;否则,返回false
    if (L.length == 0) return false; //表空,中止操作返回
    value = L.data[0];
    int pos = 0;    //假定0号元素的值最小
    //循环,寻找具有最小值的元素
    for (int i = 1; i < L.length; i++){
        //利用value记录当前具有最小值的元素
        if (L.data[i] < value){
            value = L.data[i];
            pos = i;
        }
    }
    //空出来的位置由最后一个元素填补
    L.data[pos] = L.data[L.length - 1];
    L.length--;
    //此时,value即为最小值
    return true;
}

2.设计一个高效的算法,将顺序表的所有元素逆置,要求算法的空间复杂度为O(1).
//思想:扫描顺序表L的前半部分元素,对于元素L.data[i](0<i<L.length/2),
//将其余后半部分对应元素L.data[L.length-i-1]进行交换

void Reverse(SqList &L){
    //实现元素逆置
    ElemType temp;//辅助变量
    for (int i = 0; i < L.length/2; i++){
        temp = L.data[i];
        L.data[i] = L.data[L.length-i-1];
        L.data[L.length-i-1] = temp;
    }
}

3.长度为n的顺序表L,编写一个时间复杂度为O(n),空间复杂度为O(1)的算法,该算法删除线性表中
所有值为x的数据元素.
//思想:用k记录顺序表L中不等于x的元素个数(即需要保存的元素个数),边扫描L边统计k
//并将不等于x的元素向前放置k位置上,最后修改L的长度.
void del_x(SqList &L, ElemType x){
    //删除顺序表L中所有值为x的数据元素
    int k = 0;
    for (int i = 0; i < L.length; i++){
        if (L.data[i] != x){
            L.data[k] = L.data[i];
            k++;
        }
    }

}

4.从有序顺序表中删除其值在给定值s与t之间(要求s<t)的所有元素.如果s或t不合理或者
顺序表为空则显示出错信息并退出运行.
//思想:先寻找值大于等于s的第一个元素(第一个删除的元素),然后寻找值>t的第一个元素
//(最后一个删除的元素的下一个元素),要将这段元素,则只需直接将后面的元素前移即可.
bool Del_s_t(SqList &L,ElemType s, ElemType t){
    //删除有序顺序表L中值在给定值s与t之间的所有元素
    int i,j;
    if (s >= t || L.length == 0) return false;
    //寻找值>=s的第一个元素
    for (i = 0; i < L.length && L.data[i] < s; i++)
        //所有元素值均小于s,则返回
        if (i >= L.length) return false;
    //寻找值>t的第一个元素
    for (j = i; j < L.length && L.data[j] <= t; j++);
    for (;j < L.length; i++,j++)
        L.data[i] = L.data[j];//前移,填补被删元素位置
    L.length = i+1;
    return true;    
}


5.从顺序表中删除其值在s与t之间(包含s和t,要求s<t)的所有元素,如果s或t不合理或者
顺序表为空则显示出错信息并退出运行.
//思想:从前向后扫描顺序表L,用k记录下元素值在s到t之间元素的个数(初始时k=0)
//对于当前扫描的元素,若其值不在s到t之间,则前移k个位置;
//否则执行k++,由于这样每个不在s到t之间的元素仅移动一次.所以算法效率高.
bool Del_s_t(SqList &L, ElemType t){
    //删除顺序表L中值在给定值s与t之间(s<t)的所有元素
    int i,k = 0;
    if (L.length == 0 || s >= t) return false;//线性表为空或s>t不合法,返回
    for (int i = 0; i < L.length; i++){
        if (L.data[i] >= s && L.data[i] <= t){
            k++;
        } else {
            L.data[i-k] = L.data[i];//当前元素前移动k个位置
        }
    }//for
    L.length--k;//长度减小
    return true;
}

6.从有序顺序表中删除所有其值重复的元素,使表中所有元素的值均不同.
//思想:注意到是有序顺序表,值相同的元素一定在连续的位置上,用类似于直接插入排序的思想,
//初始化时将第一个元素看做非重复的有序表.之后依次判断后面的元素是否与前面非重复有序
//表的最后一个元素相同,若如果相同则继续向后判断,如果不同则插入到前面的非重复有序表的
//最后,直至判断到表尾为止.
bool Delete_Same(SeqList &L){
    if (L.length == 0) return false;
    int i,j;//i存储第一个不相同的元素,j为工作指针
    for (i = 0,j = 1; j < L.length; j++){
        //查号下一个与上个元素值不同的元素
        if (L.data[i] != L.data[j]){
            //找到后,则将元素前移
            L.data[++i] = L.data[j];
        }
    }
    L.length  = i + 1;
    return true
}


7.将两个有序顺序表合并成一个新的有序顺序表,并由函数返回结果顺序表.
//思想:首先,按照顺序不断取下两个顺序表表头较小的结点存入新的顺序表中.
//然后,看哪个表还有剩余,把剩余的部分加到新的顺序表后面

bool Merge(SeqList A,SeqList B,SeqList &C){
    //合并有序顺序表A和B成为一个新的有序顺序表C
    if (A.length + B.length > C.maxSize) //大于顺序表的最大长度
        return false;
    int i = 0,j = 0, k = 0;
    //循环两两比较,小者存入结果表
    while (i < A.length && j < B.length){
        if (A.data[i] <= B.data[j]){
            C.data[k++] = A.data[i++];
        } else {
            C.data[k++] = B.data[j++];
        }
    }
    //还剩一个没有比较完的顺序表
    while (i < A.length){
        C.data[k++] = A.data[i++];
    }
    while (j < B.length){
        C.data[k++] = B.data[j++];
    }
    C.length = k + 1;
    return true; 
}

8.已知在一维数组A[m+n]中依次存放着两个线性表(a1,a2,a3,...,am)和(b1,b2,..,bn)
试编写一个函数,将数组中两个顺序表的位置互换,即将(b1,b2,..,bn)放在(a1,a2,..,am)
的前面.
//思想:先将数组中的全部元素原地逆置,再对前n个元素和后m个元素分别识别逆置算法
//就可以得到,从而实现顺序表的位置互换
typedef int DataType;
void Reverse(DataType A[], int left, int right, int arraySize){
    //逆置翻转
    if (left >= right || right >= arraySize) return;
    int mid = (left+right) /2 ;
    for (int i = 0; i < mid - left; i++){
        DataType temp = A[left+i];
        A[left+i] = A[right-i]
        A[right-i] = temp;
    }
}

void Exchange(DataType A[], int m, int n, int arraySize){
    //顺序表互换
    Reverse(A,0,m+n-1,arraySize);
    Reverse(A,0,n-1,arraySize);
    Reverse(A,n,m+n-1,arraySize);
}

9.线性表(a1,a2,a3,..,an)中元素递增有序且按顺序存储于计算机内.要求设计一算法完成
用最少时间在表中查找数值为x的元素,若找到将其与后继元素位置相互交换,若找不到将其插入
表中并使表中元素仍递增有序.
//思想:顺序存储的线性表递增有序,可以顺序查找,也可折半查找
void SearchExchangeInsert(ElemType A[], ElemType x){
    int low = 0,high = n-1,mid;//low和high指向顺序表下界和上界的下标
    while (low < high){
        mid = (low+high) / 2;//找中间位置
        if (A[mid] == x) break;//找到x,退出循环
        else if (A[mid]<x) low = mid + 1;//查找中点的左部分
        else high = mid -1;//查找中点的右部分
    }   
    //若最后一个元素与x相等,则不存在与其后继交换的操作
    if (A[mid] == x && mid != n-1){
        t = A[mid];
        A[mid] = A[mid+1];
        A[mid+1] = t;
    }
    //查找失败,插入数据元素x
    if (low > high){
        //后移元素
        for (i = n - 1; i > high; i--){
            A[i+1] = A[i];
        }
        //插入x
        A[i+1] = x;
    }//结束charu
    //程序终止
}

10.[2010年计算机联考真题]
设将n(n>1)个整数存放到一维数组R中.试设计一个在时间和空间两方面都尽可能高效的算法.
将R中保存的序列循环左移p(0<p<n)个位置,即将R中的数据由(x0,x1,..,xn-1)变换为
(xp,xp+1,..,xn-1,x0,x1,..,xp-1).
要求:
(1)给出算法的基本设计思想
(2)根据设计思想,采用C或C++语言描述算法,关键之处给出注释.
(3)说明你设计算法的时间复杂度和空间复杂度
//思想:
//Reverse(0,p-1)得到cbadefgh
//Reverse(p,n-1)得到cbahgfed
//Reverse(0,n-1)得到defghabc
void Reverse(int R[], int from, int to){
    int i,temp;
    for (i = 0; i < (to-from+1)/2; i++){
        temp = R[from+1];
        R[from+i] = R[to-i];
        R[to-i] = temp;
    }
}//Reverse

void Converse(int R[], int n, int p){
    Reverse(0,p-1);
    Reverse(p,n-1);
    Reverse(0,n-1);
}
//时间复杂度分别为O(p/2),O((n-p)/2),O(n/2)

11.[2011年计算机联考真题]
一个长度为L(L>1)的升序序列S,处在[L/2]个位置的数称为S的中位数.
例如,若序列S1 = (11,13,15,17,19),则S1的中位数为15.
两个序列的中位数是含它们所有元素的升序序列的中位数.
例如,若S2=(2,4,6,8,20),则S1和S2的中位数为11.
现在有两个等长升序序列A和B,试设计一个在时间和空间两个方面都尽可能高效的算法,找出
两个序列A和B的中位数.
要求:
(1)给出算法的基本设计思想
(2)根据设计思想,采用C或C++语言描述算法,关键之处给出注释.
(3)说明你设计算法的时间复杂度和空间复杂度
//思想:
//分别求两个升序序列A,B的中位数,设为a和b,求序列A,B的中位数如下:
//1.若a=b,则a或b即为所求中位数,算法结束
//2.若a<b,则舍弃序列A中较小的一半,同时舍弃序列B中较大的一半,要求两个设计的长度相等
//3.若a>b,则舍弃序列A中较大的一半,同时舍弃序列B中较大的一半,要求两个舍弃的长度相等
int M_Search(int A[], int B[], int n){
    int s1 = 0,d1 = n-1,m1;
    int s2 = 0,d2 = n-1,m2;
    //分别表示序列A和序列B的首位数,末尾数和中位数
    while (s1 != d1 || s2 != d2){
        m1 = (s1+d1)/2;
        m2 = (s2+d2)/2;
        if (A[m1] == B[m2]) //满足条件1 
            return A[m1];
        if (A[m1] < B[m2]){//满足条件2
            if ((s1+d1)%2 == 0){//若元素个数为奇数
                s1 = m1;//舍弃A中间点以前的部分且保留中间点
                d2 = m2;//舍弃B中间点以后的部分且保留中间点
            } else {//若元素为偶数
                s1 = m1 + 1;//舍弃A中间点以前的部分且保留中间点
                d2 = m2;//舍弃B中间点以后的部分且保留中间点
            }
        }
        else {//满足条件3
            if ((s2+d2)%2 == 0){//若元素个数为奇数
                d1 = m1;//舍弃A中间点以前的部分且保留中间点
                s2 = m2;//舍弃B中间点以后的部分且保留中间点
            } 
            else {
                d1 = m1;//舍弃A中间点以前的部分且保留中间点
                s2 = m2 + 1;//舍弃B中间点以后的部分且保留中间点
            }
        }
    }
    return A[s1] < B[s2] ? A[s1]:B[s2];
}

12.[2013年计算机联考真题]
已知一个整数序列A=(a0,a1,..,an-1),其中0<ai<n(0<i<n).若存在ap1 = ap2 = .. = apm = x
且m > n/2(0<pk<n,1<k<m)则称x为A的主元素.例如A= (0,5,5,3,5,7,5,5),则5为主元素;
又如A=(0,5,5,3,5,1,5,7),则A中没有主元素.假设A中的n个元素保存在一个一维数组中,请设计
一个尽可能高效的算法,找出A的主元素.若存在主元素,则输出该元素;否则输出-1. 
要求:
(1)给出算法的基本设计思想
(2)根据设计思想,采用C或C++语言描述算法,关键之处给出注释.
(3)说明你设计算法的时间复杂度和空间复杂度
//思想:
//笨算法的策略是从前往后扫描数组元素,标记出一个可能成为主元素的元素Num.
//然后重新计数,确认Num是否为元素
//算法分为以下两步:
//1.选取候选的主元素:依次扫描所给的数组中的每个整数,将第一个遇到的整数Num保存到c中
//记录Num的出现的次数为1;若遇到下一个整数仍等于Num,则计数加1,否则计数减1;
//当计数减到0时,将遇到的下一个整数保存在c中,计数重新记为1,开始新的一轮计数
//即从当前位置开始重复上述过程,直到扫描完全部数组元素.

//2.判断c中元素是否是真的主元素:再次扫描该数组,统计c中元素出现的次数,若大于n/2,
//则为主元素;否则,序列中不存在主元素
int Majority(int A[], int n){
    int i,c,count = 1;//c用来保存候选的主元素,count用来计数
    c = A[0];//设置A[0]为候选主元素
    for (i = 1; i < n; i++)
        if (A[i] == c){//对A中的候选主元素进行计数
            count++;
        }
        else {
            if (count > 0)//处理不是候选主元素的情况
                count--;
            else {//重新更换候选主元素,重新计数
                c = A[i];
                count = 1;
            }
        }

        if (count > 0)
            for (i = count = 0; i < n; i++)//统计候选主元素的实际出现次数
                if (A[i] == c)
                    count++;
        if (count > n/2) return c;//确认候选主元素
        else return -1;//不存在主元素
}


线性表的链式表示
单链表的结点类型描述:
typedef struct LNode{   //定义单链表结点类型
    ElemType data;      //数据域
    struct LNode *next; //指针域
}LNode,*LinkList;

双链表的结点类型描述:
typedef struct DNode{   //定义双链表结点类型
    ElemType data;      //数据域
    struct DNode *prior,*next; //前驱和后继指针
}DNode,*DLinkList;

静态链表结点类型的描述:
#define MaxSize 50  //静态链表的最大长度
typedef struct {    //静态链表结构类型的定义
    ElemTypen data; //存储数据元素
    int next;       //下一个元素的数组下标
} SLinkList[MaxSize];

程序设计题
1.设计一个递归算法,删除不带头结点的单链表L中所有值为x的结点

终止条件:f(L,x) = 不做任何事情 //若L为空表
递归主体:f(L,x) = 删除*L结点;
                 f(L->next,x) //若L->data = x
                 f(L,x) = f(L->next,x)//其他情况
void Del_x(LinkList &L,ElemType x){
    //递归实现在单链表L中删除值为x的jied
    LNode *p;               //p指向待删除结点
    if (L == NULL) return;  //递归出口
    if (L -> data == x){    //若L所指结点的值为x
        p = L;              //删除*L,并让L指向下一结点
        L = L -> next;
        free(p);
        Del_x(L,x);         //递归调用
    } else {                //若L所指的结点的值不为x
        Del_x(L->next,x);   //递归调用
    }
}
算法需要借助一个递归工作栈,深度为O(n),时间复杂度为O(n).

2.在带头结点的单链表L中,删除所有值为x的结点,并释放其空间.
假设值为x的结点不唯一,试编写算法以实现上述操作.
//思想:用p从头至尾扫描单链表,pre指向*p结点的前驱.
//若p所指结点的值为x,则删除,并让p移向下一个结点
//否则让pre,p指针同步后移一个结点.

void Del_x(LinkList &L,ElemType x){
    //L为带头结点的单链表,本算法删除L中所有值为x的结点
    LNode *p = L -> next,*pre=L,*q; //置p和pre的初始值
    while (p != NULL){
        if (p->data == x){
            q = p;           //q指向该结点
            p = p->next;    
            pre -> next = p; //删除*q结点
            free(q);         //释放*q结点的空间
        } 
        else {               //否则,pre和p同步后移
            pre = p;
            p = p -> next;
        }//else
    }//while
}


3.设L为带头结点的单链表,编写算法实现从尾到头反向输出每个结点的值
//思想:利用栈和递归的思想来实现,每当访问一个结点时,先递归输出它后面的结点,再输出该结点自身
void R_Print(LinkList L){
    //从尾到头输出单链表L中每个结点的值
    if (L->next != NULL){
        R_Print(L->next);//递归
    }//if
    print(L->data);//输出函数
}


4.试编写在带头结点的单链表L中删除一个最小值界定啊的高效算法(假设最小值结点是唯一的)
//思想:用p从头至尾扫描单链表,pre指向*p结点的前驱,用minp保存值最小的结点指针(初值为p)
//minpre指向*minp结点的前驱(初值为pre).一边扫描,一边比较.
//若p->data小于minp->data,则将p,pre分别赋值给minp,minpre.
//当p扫描完毕时,minp指向最小值结点.
//minpre指向最小值结点的前驱结点,再将minp所指结点删除即可
LinkList Delete_Min(LinkList &L){
    //L为带头结点的单链表,本算法删除其最小值结点
    LNode *pre = L,*p = pre->next;  //p为工作指针,pre指向其前驱
    LNode *minpre = pre,*minp = p;  //保存最小值结点及其前驱
    while (p != NULL){
        if (p -> data < minp -> data){
            minp = p;       //找到比之前找到的最小值结点更小的结点
            minpre = pre;   
        }
        pre = p;            //继续扫描下一个结点
        p = p -> next;
    }
    minpre -> next = minp -> next;//删除最小值结点
    free(minp);
    return L;
}


5.试编写算法将带头结点的单链表就地逆置,所谓就地是指辅助空间复杂度为O(1).
//思想:将头结点摘下,然后从第一结点开始,依次前插入到头结点的后面
//直到最后一个结点为止,则实现了链表的逆置
LinkList Reverse(LinkList L){
    //L是带头结点的单链表,将L就地逆置
    LNode *p,*r;                //p为工作指针,r为p的后继,以防断链
    p = L -> next;              //从第一个元素结点开始
    L -> next = NULL;           //先将头结点L的next域置为NULL
    while (p != NULL){          //依次将元素结点摘下
        r = p -> next;          //暂存p的后继
        p -> next = L -> next;  //将p结点插入到头结点之后
        L -> next = p;
        p = r;
    }
    return L;
}


6.试编写算法将带头结点的单链表L,设计一个算法使其元素递增有序.
//思想:采用直接插入排序算法的思想,先构成只含一个数据结果的有序单链表,然后依次扫描单链表
//中剩下的结点*p(直至p==NULL),在有序表中通过比较查找插入*p的前驱结点*pre
//然后将*p插入到*pre之后.
void Sort(LinkList &L){
    LNode *p = L -> next,*pre;
    LNode *r = p -> next;
    p -> next = NULL;
    p = r;
    while (p != NULL){
        r = p -> next;
        pre = L;
        while (pre->next != NULL && pre->next->data < p->data){
            pre = pre -> next;      //在有序表中查找插入*p的前驱结点*pre
        p -> next = pre -> next;    //将*p插入到*pre之后
        pre -> next = p;        
        p = r;                      //扫描原单链表中剩下的结点
    }
}

7.设在带表头结点的单链表中所有元素结点的数据值无序,试编写一个函数,删除表中所有介于给定
的两个值(作为函数参数给出)之间的元素的元素(若存在)

void RangeDelete(LinkList &L, int min, int max){
    LNode *pr = L,*p = L->link;     //p是检测指针,pr是其前驱
    while (p != NULL){
        if (p->data > min && p ->data < max){ //寻找到被删结点,删除
            pr->link = p ->link;
            free(p);
            p = pr -> link;
        }
        else {  //否则继续寻找被删除结点
            pr = p;
            p = p -> link;
        }
    }
}

8.给定两个单链表,编写算法找出两个链表的公共结点
//思想:先分别遍历两个链表得到它们的长度,并求长度之差.
//在长链表上先遍历长度之差个结点之后,再同步遍历两个链表
//知道找到相同的结点,或者一直到链表结束.
LinkList Search_lst_common(LinkList L1, LinkList L2){
    //分别计算两个链表的表长
    int len1 = L1.length;
    int len2 = L2.length;
    LinkList longList,shortList;//分别指向表长较长和表长较短的链表
    if (len1 > len2){
        longList = L1 -> next;
        shortList = L2 -> next;
        int dist = len1 - len2 ;
    } else {
        longList = L2 -> next;
        shortList = L1 -> next;
        int dist = len2 - len1;
    }
    while (dist--)
        longList = longList -> next;
    while (longList != shortList){
        if (longList == shortList)
            return longList;
        else {
            longList = longList -> next;
            shortList = shortList -> next;
        }
    }//while
    return NULL;
}


9.给定一个带表头结点的单链表,设head为头指针,结点结构为(data,next)
data为整型元素,next为指针,试写出算法:按递增次序输出单链表中各结点的数据元素,
并释放结点所占的存储空间(要求:不允许使用数组作为辅助空间)
//思想:对链表进行遍历,在每趟遍历中查找出整个链表的最小值元素,输出并释放结点所占空间;
//再查找次小值元素,输出并释放空间,如此下去,直到链表为空,最后释放头结点所占存储空间
void Min_Delete(LinkList &head){
    //循环到仅剩头结点
    while (head -> next != NULL){
        pre = head;             //pre为元素最小值结点的前驱结点的指针
        p = pre -> next;        //p为工作指针
        while (p -> next != NULL){
            if (p->next->data < pre->next->data){
                pre = p;        //记住当前最小值结点的前驱
                p = p -> next;  
            }
        }
        print(pre->next->data); //输出元素最小值结点的数据
        u = pre -> next;        //删除元素值最小的结点,释放结点空间
        pre -> next = u -> next;
        free(u);
    }//while    
    free(head);                  //释放头结点
}


10.将一个带头结点的单链表A分解为两个带头结点的单链表A和B,使得A表中含有原表中序号为
奇数的元素,而B表中含有原表中序号为偶数的元素,且保持其相对顺序不变.
//思想:设置一个访问序号变量(初始值为0),每访问一个结点序号自动加1,然后根据序号的奇偶性
//将结点插入到A表或者B表中.重复以上操作直到表尾
LinkList DisCreate(LinkList &A){
    int i = 0;              //i记录表A中结点的序号
    B = (LinkList)malloc(sizeof(LNode)); //创建B表表头
    B -> next = NULL;                    //B表的初始化
    LNode *ra = A,*rb = B;               //ra和rb分别指向将创建的A表和B表的尾结点

    p = A -> next;          //p为链表工作指针,指向待分解的结点
    A -> next = NULL;       //置空新的A表
    while (p != NULL){
        i++;                //序号+1
        if (i%2 == 0){      //处理序号为偶数的链表结点
            rb -> next = p; //在B表尾插入新结点
            rb = p;         //rb指向新的尾结点
        }
        else {              //处理原序号为奇数的结点
            ra -> next = p; //在A表尾插入新结点
            ra = p;
        }
        p = p -> next;      //将p恢复为指向新的待处理结点
    }//while结束       
    ra -> next = NULL;
    rb -> next = NULL;
    return B;
}


11.设C={a1,b2,a2,b2,...,an,bn}为线性表,采用带头结点的hc单链表存放,设计一个就地
算法,将其拆分为两个线性表,使得
A = {a1,a2,...,an}, B = {bn,bn-1,...,bn,b1}
LinkList DisCreate(LinkList &L){
    LinkList B = (LinkList)malloc(sizeof(LNode));
    B -> next = NULL;           //B表的初始化
    LNode *p = A -> next,*q;    //p为工作指针
    LNode *ra = A;              //ra指向A的A的尾结点
    while (p != NULL){          
        ra -> next = p;         //将*p链到A的末尾
        ra = p;
        p = p -> next;          //头插后,*p将断链,因此用q以及*p的后继
        q = p -> next;          //将*p插入到B
        p -> next = B -> next;
        B -> next = p;
        p = q;
    }
    ra -> next = NULL;          //A尾结点的next域置空
    return B;
}


12.在一个递增有序的线性表中,有数值相同的元素存在.若存储方式为单链表,
设计算法去掉数值相同的元素,使表中不再有重复的元素.例如(7,10,10,21,30,42,42,42,51,70)
将变作(7,10,21,30,42,51,70)
void Del_Same(LinkList &L){
    LNode *p = L -> next,*q;
    if (p== NULL) 
        return ;
    while (p->next != NULL) {
        q = p -> next;                  //q指向*p的后继结点
        if (p -> data == q -> data){    //找到重复值的结点    
            p -> next = q -> next;      //释放*q结点
            free(q);                    //释放相同元素值的结点
        } else {
            p = p -> next;
        }
    }
}


13.假设有两个按元素值递增次序排列的线性表,均以单链表存储.
请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表,并要求排列原来两个单链表
的结点存放归并后的单链表.
//思想;两个链表已经按元素值递增次序排序,将其合并时,均从第一个结点起进行比较,将小的结点链入
//链表之中,同时后移工作指针.要求结果链表按元素递减次序排列,因此新链表的建立方式应该用头插法
//比较结束后,可能会有一个链表非空,此时用头插法将剩下的结点依次插入新链表即可
void MergeList(LinkList &La, LinkList &Lb){
    //合并两个递增有序的链表,并使合并后的链表递减排列
    LNode *r,*pa = LA -> next,*pb = Lb -> next;
    La -> next =NULL;
    while (pa && pb){
        if (pa -> pb <= pb-){
            r = pa-> next;
            pa -> next = La -> next;
            La -> next = pa;
            pa = r;
        }
        else {
            r = pb -> next;
            pb -> next = La -> next;
            La -> next = pb
        }
    }
}


14.设A和B是两个单链表(带头结点),其中元素递增有序.设计一个算法从A和B中公共元素产生单链表C,
要求不破坏A,B的结点.
//思想:表A,B都有序,可以从第一个元素起依次比较A,B两个表的元素,若元素值不等,
//则值小的指针往后移动,若元素值相等,则创建一个值等于两个结点的元素值的新的结点,
//使用尾插法插入到新的链表,并且两个原表指针往后移动一位.直到其中一个链表遍历到表尾.
void Get_Common(LinkList A,LinkList B){
    LNode *p = A -> next,*q = B -> next,*r,*s;
    LinkList C = (LinkList)malloc(sizeof(LNode));//建立表C
    r = C;    //r始终指向C的尾结点
    //循环跳出条件
    while (p != NULL && q != NULL){
        if (p -> data < q -> data)
            p = p -> next;  //若A的当前元素较小,后移指针
        else if (p->data > q->data)
            q = q -> next;  //若B的当前较小,后移较小
        else {              //找到公共元素结点
            s = (LNode*)malloc(sizeof(LNode));  //复制产生结点*s
            s -> data = p -> data;      //将*s链接到C上
            r -> next = s;
            r = s;
            p = p -> next;              //表A和表B继续向后扫描
            q = q -> next;
        } 
        r -> next = NULL;               //置C尾结点指针为空
    }
}

15.已知两个链表A和B分别表示两个集合,其元素递增排列.编制函数,求A与B的交集,并存放于A链表中.
LinkList Union(LinkList &La, LinkList &Lb){
    pa = La -> next;
    pb = Lb -> next;
    pc = La;
    while (La && Lb){
        if (pa -> data == pb-> data){
            pc -> next = pa;
            pc = pa;
            pa = pa -> next;
            u = pb;
            pb = pb -> next;
            free(u);
        } else if (pa->data < pb->data){
            u = pa;
            pb = pb -> next;
            free(u);
        }
    }//while
    while (pb){
        u = pb;
        pb = pb -> next;
        free(u);
    }
    pc -> next = NULL;
    free(Lb);
    return La;
}

16.两个整数序列A=a1,a2,a3,..,am和B=b1,b2,b3,...,bn已经存入两个单链表中.
设计一个算法,判断序列B是否是序列A的连续子序列.
int Pattern(LinkList A, LinkList B){
    LNode *p = A;       
    LNode *pre = p;
    LNode *q = B;
    while (p && q)
        if (p->data == q->data){
            p = p -> next;
            q = q -> next;
        } else [
            pre = pre -> next;
            p = pre;
            q = B;
        ]
    if (q == NULL)
        return 1;
    else 
        return 0;
}

17.设计一个算法用于判断带头结点的循环双链表是否对称
int Symmetry(DLinkList L){
    DNode *p = L->next,*q = L->prior;
    while (p != q && q->next != p)
        if (p->data==q->data){
            p = p -> next;
            q = q -> prior;
        }
        else {
            return 0;
        }
    return 1;
}


18.有两个循环单链表,链表的头指针分别为h1和h2,编写一个函数将链表h2链接到链表h2之后,
要求链接后的链表仍保持循环链表形式.
LinkList Link(LinkList &h1, LinkList &h2){
    LNode *p,*q;
    p = h1;
    while (p->next != h1)
        p = p -> next;
    q = h2;
    while (q -> next != h2)
        q = q -> next;
    p -> next = h2;
    q -> next = h1;
    return h1;
}


19.设有一个带头结点的循环单链表,其结点值均为正整数.设计一个算法,反复找出单链表中结点值
最小的结点并输出,然后将该结点从中删除,直到单链表空为止,再删除表头结点.

void Del_All(LInkList &L){
    LNode *p,*pre,*minp,*minpre;
    while (L->next != L){
        p = L->next;
        pre = L;
        while (p != L){
            if (p->data < minp->data){
                minp = p;
                minpre = pre;
            }
            pre = p;
            p = p -> next;
        }
        printf("%d",minp->data);
        minpre->next = minp->next;
        free(minp)l
    }
    free(L);
}


20.设头指针为L的带有表头指针的非循环双向链表,其每个结点中除有pred(前驱指针),data(数据)
和next(后继指针)域外,还有一个访问频度域freq.在链表被启用前,其值均初始化为0.
每当在链表中进行依次Locate(L,x)运算时,令元素值为x的结点中freq域的值增1,并使此链表中结点
保持按访问频度非增(递减)的顺序排列,同时最近访问的结点排在频度相同的结点的前面,以便使频繁访问
的结点总是靠近表头.试编写符合上述要求的Locate(L,x)运算的算法,该运算为函数过程,返回找到
结点的地址,类型为指针型.
DLinkList Locate(DLinkList &L, ElemType x){
    DNode *p = L->next,*q;
    while (p && p->data != x)
        p = p -> next;
    if (!p){
        exit(0);
    }
    else {
        p -> freq++;
        p -> next -> pred = p -> pred;
        p -> pred -> pred = p -> next;
        q = p -> pred;
        while (q != L && q -> freq)
            q = q -> pred;
        p -> next = q -> next;
        q -> next -> pred = p;
        p -> pred = q;
        q -> next = p;
    }
    return p;
}