title: 【锐格】数据结构-线性表
tags:

  • 锐格
  • C
  • 链表
    abbrlink: 2eb647a7
    date: 2021-09-21 11:11:21

欢迎加入NEFU计算机编程交流群：523539085

顺序表

4882

  1. #include<iostream>
  2. #include<stdlib.h>
  3. using namespace std;
  5. const int defaultSize = 10;
  7. class SeqList {
  8. protected:
  9.     int *data;
  10.     int maxSize; //表最大可容纳项数
  11.     int last; //当前表大小
  12. public:
  13.     SeqList(int sz = defaultSize);
  14.     SeqList(SeqList &l);
  15.     ~SeqList();
  16.     int Length() const; //计算表长度
  17.     int getData(int i) const; //取第i歌表项的值，存放在x中
  18.     void setData(int i,int x);
  19.     bool Insert(int i,int x); //插入x在第i歌表项之后
  20.     void Remove(int i);
  21.     void output(); // 输出顺序表
  22. };
  24. SeqList::SeqList(int sz)
  25. {
  26.     if (sz>0) {
  27.         maxSize = sz;
  28.         last = -1;
  29.         data = new int[maxSize];
  30.         if (data == NULL)
  31.             exit(1);
  32.     }
  33. }
  35. SeqList::~SeqList()
  36. {
  37.     delete []data;
  38. }
  40. int SeqList::Length() const
  41. {
  42.     return last+1;
  43. }
  45. int SeqList::getData(int i) const
  46. {
  47.     return data[i];
  48. }
  50. void SeqList::setData(int i,int x)
  51. {
  52.     data[i] = x;
  53. }
  55. bool SeqList::Insert(int i,int x)
  56. {
  57.     if (last == maxSize-1)
  58.         return false;
  59.     if (i<0||i>last+1)
  60.         return false;
  61.     int j;
  62.     for (j=last;j>=i;j--)
  63.         data[j+1] = data[j];
  64.     data[i] = x;
  65.     last++;
  66.     return true;
  67. }
  69. void SeqList::Remove(int i)
  70. {
  71.     int j;
  72.     for (j=i;j<=last-1;j++)
  73.         data[j] = data[j+1];
  74.     last--;
  75. }
  77. void SeqList::output()
  78. {
  79.     int i;
  80.     for (i=0;i<=last;i++)
  81.         cout << data[i] << " ";
  82.     cout << endl;
  83. }
  85. //write your code here
  88. int main()
  89. {
  90.     int n,m,i,x;
  91.     cin >> n >> m;//输入两个表的长度
  92.     SeqList l1(n),l2(m);
  93.     for (i=0;i<n;i++) {
  94.         cin >> x;
  95.         l1.Insert(i,x);//list1
  96.     }
  97.     for (i=0;i<m;i++) {
  98.         cin >> x;
  99.         l2.Insert(i,x);//list2
  100.     }
  101.     //write your code here
  102.     int len=min(n, m);
  103.     int cnt=0;
  104.     for(int i=0;i<len;i++)
  105.     {
  106.         if(l1.getData(0)==l2.getData(0))
  107.         {
  108.             cout<<l1.getData(0)<<" ";
  109.             cnt++;
  110.             l1.Remove(0);
  111.             l2.Remove(0);
  112.         }
  113.     }
  114.     cout<<endl;
  115.     if(l1.Length()==0 && l2.Length()==0)
  116.     {
  117.         cout<<"="<<endl;
  118.     }
  119.     else if(l1.Length()<=0 || l1.getData(0)<l2.getData(0))
  120.     {
  121.         cout<<"<"<<endl;
  122.     }
  123.     else
  124.     {
  125.         cout<<">"<<endl;
  126.     }
  127.     return 0;
  128. }

4314

这个merge方式用for循环思索了很久还是觉得很难实现，只好用while代替之了

  1. #include <stdio.h>
  2. #include <stdlib.h>
  4. #define MAXSIZE 100
  5. #define TRUE 1
  6. #define FALSE 0
  8. typedef int Status;
  10. typedef struct SeqList{
  11.     int data[MAXSIZE];
  12.     int last; //当前表大小
  13. }SeqList, *pSeqList;
  15. const int Length(const pSeqList l)
  16. {
  17.     return l->last+1;
  18. }
  20. const int getData(const pSeqList l, int i)
  21. {
  22.     return l->data[i];
  23. }
  25. void setData(pSeqList l, int i,int x)
  26. {
  27.     if(i >= 0 && i <= l->last)
  28.         l->data[i] = x;
  29. }
  31. Status Insert(pSeqList l, int i, int x)
  32. {
  33.     // write your code here
  34.     for (int j=l->last;j>=i;j--)
  35.         l->data[j+1] = l->data[j];
  36.     l->data[i] = x;
  37.     l->last++;
  38. }
  40. void output(const SeqList l)
  41. {
  42.     int i;
  43.     for (i=0;i<=l.last;i++)
  44.     {
  45.         printf("%d ", l.data[i]);
  46.     }
  47.     printf("\n");
  48. }
  50. void mergeSeqList(const pSeqList l1,const pSeqList l2, pSeqList l)
  51. {
  52.     // write your code here
  53.     int len, cnt1=0, cnt2=0;
  54.     len=Length(l1)+Length(l2);
  55.     int l1v=getData(l1, cnt1), l2v=getData(l2, cnt2);
  56.     int i=0;
  57.     while(cnt1< Length(l1) && cnt2<Length(l2))
  58.     {
  59.         if(l1v <= l2v)
  60.         {
  61.             Insert(l, i++, l1v);
  62.             l1v=getData(l1, ++cnt1);
  63.         }
  64.         else
  65.         {
  66.             Insert(l, i++, l2v);
  67.             l2v=getData(l2, ++cnt2);
  68.         }
  69.     }
  70.     if(cnt1<Length(l1))
  71.         while(i<len)
  72.         {
  73.             Insert(l, i++, l1v);
  74.             l1v=getData(l1, ++cnt1);
  75.         }
  76.     else
  77.         while(i<len)
  78.         {
  79.             Insert(l, i++, l2v);
  80.             l2v=getData(l2, ++cnt2);
  81.         }
  82. }
  84. int main()
  85. {
  86.     int n,m,i,x;
  87.     scanf("%d", &n);
  88.     scanf("%d", &m);
  89.     SeqList l1, l2;
  90.     l1.last = -1;
  91.     l2.last = -1;
  92.     for (i=0;i<n;i++) {
  93.         scanf("%d", &x);
  94.         Insert(&l1, i, x);
  95.     }
  96.     for (i=0;i<m;i++) {
  97.         scanf("%d", &x);
  98.         Insert(&l2, i, x);
  99.     }
  100.     SeqList l;
  101.     l.last = -1;
  102.     mergeSeqList(&l1,&l2,&l);
  103.     output(l);
  104.     return 0;
  105. }

4880

正确输出：4 9 6 2 7

我的输出：4 6 2 7 9

但是样例上面写的又和我一致，就很迷惑【锐格】数据结构-线性表 - 图1

破案了，样例给错了，正确样例应该是数据里面的，还有主函数里面调用函数需要自己去调整顺序…这锐格真的让人迷惑

  1. #include<iostream>
  2. #include<stdlib.h>
  3. using namespace std;
  5. const int defaultSize = 10;
  7. class SeqList {
  8. protected:
  9.     int *data;
  10.     int maxSize; //表最大可容纳项数
  11.     int last; //当前表大小
  12. public:
  13.     SeqList(int sz = defaultSize);
  14.     ~SeqList();
  15.     int Length() const; //计算表长度
  16.     int getData(int i) const; //取第i歌表项的值，存放在x中
  17.     void setData(int i,int x);
  18.     bool Insert(int i,int &x); //插入x在第i歌表项之后
  19.     void Remove(int i);
  20.     void DeleteAllx(int x);
  21.     int deleteMin();
  22.     void deleteDuplication();
  23.     void output(); // 输出顺序表
  24. };
  26. SeqList::SeqList(int sz)
  27. {
  28.     if (sz>0) {
  29.         maxSize = sz;
  30.         last = -1;
  31.         data = new int[maxSize];
  32.         if (data == NULL)
  33.             exit(1);
  34.     }
  35. }
  37. SeqList::~SeqList()
  38. {
  39.     delete []data;
  40. }
  42. int SeqList::Length() const
  43. {
  44.     return last+1;
  45. }
  47. int SeqList::getData(int i) const
  48. {
  49.     return data[i];
  50. }
  52. void SeqList::setData(int i,int x)
  53. {
  54.     data[i] = x;
  55. }
  57. bool SeqList::Insert(int i,int &x)
  58. {
  59.     if (last == maxSize-1)
  60.         return false;
  61.     if (i<0||i>last+1)
  62.         return false;
  63.     int j;
  64.     for (j=last;j>=i;j--)
  65.         data[j+1] = data[j];
  66.     data[i] = x;
  67.     last++;
  68.     return true;
  69. }
  71. void SeqList::Remove(int i)
  72. {
  73.     int j;
  74.     for (j=i;j<=last;j++)
  75.         data[j] = data[j+1];
  76.     last--;
  77. }
  79. //write your code here
  80. void SeqList::DeleteAllx(int x)
  81. {
  82.     for(int i=0;i<=last;i++)
  83.     {
  84.         if(getData(i)==x)
  85.             Remove(i--);
  86.     }
  87. }
  89. void SeqList::deleteDuplication()
  90. {
  91.     for(int i=0;i<=last;i++)
  92.     {
  93.         for(int j=i+1;j<=last;j++)
  94.         {
  95.             if(getData(i) == getData(j))
  96.             {
  97.                 Remove(j--);
  98.             }
  99.         }
  100.     }
  101. }
  103. int SeqList::deleteMin()
  104. {
  105.     int mininum=99999, idx=-1;
  106.     for(int i=0;i<=last;i++)
  107.     {
  109.         if(getData(i)<mininum)
  110.         {
  111.             mininum=getData(i);
  112.             idx=i;
  113.         }
  114.     }
  115.     data[idx]=data[last];
  116.     last--;
  117.     return mininum;
  118. }
  121. void SeqList::output()
  122. {
  123.     for (int i=0;i<=last;i++)
  124.         cout << data[i] << " ";
  125.     cout << endl;
  126. }
  128. int main()
  129. {
  130.     int n,i,x;
  131.     cin >> n;
  132.     SeqList l(n);
  133.     for (i=0;i<n;i++) {
  134.         cin >> x;
  135.         l.Insert(i,x);
  136.     }
  137.     l.deleteDuplication();
  138.     l.DeleteAllx(3);
  139.     l.deleteMin();
  140.     l.output();
  141.     return 0;
  142. }
  143. //3 4 1 6 4 2 4 7 3 1 2 4 6 6 9

4312

这题思路想出来以后还兴奋了一下

  1. #include<stdio.h>
  2. #include<stdlib.h>
  4. #define MAXSIZE 100
  5. #define TRUE 1
  6. #define FALSE 0
  8. typedef int Status;
  10. int data[MAXSIZE];
  11. int last = -1; //当前表大小
  13. const int Length()
  14. {
  15.     return last+1;
  16. }
  18. const int getData(int i)
  19. {
  20.         return data[i];
  21. }
  23. void setData(int i,int x)
  24. {
  25.     data[i] = x;
  26. }
  28. Status Insert(int i,int x)
  29. {
  30.     // write your code here
  31.     for(int j=last;j>=i;j--)
  32.     {
  33.         data[j+1]=data[j];
  34.     }
  35.     data[i]=x;
  36.     last++;
  37. }
  39. void output()
  40. {
  41.     // write your code here
  42.     for(int i=0;i<Length();i++)
  43.         printf("%d ", data[i]);
  44.     printf("\n");
  45. }
  47. void condense()
  48. {
  49.     // write your code here
  50.     int cnt=0;
  51.     for(int i=0;i<Length();i++)
  52.     {
  53.         if(data[i]!=0)
  54.         {
  55.             if(i!=cnt)
  56.             {
  57.                 data[cnt]=data[i];
  58.                 data[i]=0;
  59.             }
  60.             cnt++;
  61.         }
  62.     }
  63. }
  64. //2 0 10 9 4 0 2 0 0 1
  65. int main()
  66. {
  67.     int n,i,x;
  68.     scanf("%d", &n);
  70.     for (i=0;i<n;i++) {
  71.         scanf("%d", &x);
  72.         Insert(i,x);
  73.     }
  74.     condense();
  75.     output();
  76.     return 0;
  77. }

4311

双指针的经典应用

  1. #include<stdio.h>
  2. #include<stdlib.h>
  4. #define MAXSIZE 100
  5. #define TRUE 1
  6. #define FALSE 0
  8. typedef int Status;
  11. int data[MAXSIZE];
  12. int last = -1; //当前表大小
  14. const int Length()
  15. {
  16.     return last+1;
  17. }
  19. Status Insert(int i,int x)
  20. {
  21.     // write your code here
  22.     for(int j=last;j>=i;j--)
  23.     {
  24.         data[j+1]=data[j];
  25.     }
  26.     data[i]=x;
  27.     last++;
  28. }
  30. void output()
  31. {
  32.     // write your code here
  33.     for(int i=0;i<Length();i++)
  34.     {
  35.         printf("%d ", data[i]);
  36.     }
  37.     printf("\n");
  38. }
  40. void reverse()
  41. {
  42.     // write your code here
  43.     int i,j;
  44.     int tmp;
  45.     for(int i=0,j=last; i<j; i++,j--)
  46.     {
  47.         tmp=data[i];
  48.         data[i]=data[j];
  49.         data[j]=tmp;
  50.     }
  51. }
  53. int main()
  54. {
  55.     int n,i,x;
  56.     scanf("%d", &n);
  58.     for (i=0;i<n;i++) {
  59.         scanf("%d", &x);
  60.         Insert(i,x);
  61.     }
  62.     output();
  63.     reverse();
  64.     output();
  65.     return 0;
  66. }

4877

基础的增删查改的练习，但是需要辨别清楚i在0，1起点时不同的边界（debug了好久..）

  1. #include<iostream>
  2. #include<stdlib.h>
  3. using namespace std;
  5. const int defaultSize = 10;
  7. class SeqList {
  8. protected:
  9.     int *data;
  10.     int maxSize; //表最大可容纳项数
  11.     int last; //当前表大小
  12.     void reSize(int newSize); //改变data数组空间大小
  13. public:
  14.     SeqList(int sz = defaultSize);
  15.     SeqList(SeqList &l);
  16.     ~SeqList();
  17.     int Size() const; //计算表最大可容纳表项个数
  18.     int Length() const; //计算表长度
  19.     int Search(int &x) const; //搜索x在表中位置，函数返回表项序号
  20.     bool getData(int i,int &x) const; //取第i歌表项的值，存放在x中
  21.     void setData(int i,int &x); //用x修改第i个表项的值
  22.     bool Insert(int i,int &x); //插入x在第i歌表项之后
  23.     bool Remove(int i,int &x); //删除第i歌表项，用x返回其值
  24.     bool isEmpty(); //判断表是否空
  25.     bool isFull(); //判断表是否满
  26.     void output(); // 输出顺序表
  27. };
  29. //write your code here
  30. SeqList::SeqList(int sz)
  31. {
  32.     if (sz>0) {
  33.         maxSize = sz;
  34.         last = -1;
  35.         data = new int[maxSize];
  36.         if (data == NULL)
  37.             exit(1);
  38.     }
  39. }
  41. SeqList::~SeqList()
  42. {
  43.     delete []data;
  44. }
  46. int SeqList::Size() const
  47. {
  48.     return maxSize;
  49. }
  51. bool SeqList::isFull()
  52. {
  53.     if(last==maxSize)
  54.         return true;
  55.     else
  56.         return false;
  57. }
  59. int SeqList::Length() const
  60. {
  61.     return last+1;
  62. }
  64. bool SeqList::getData(int i,int &x) const
  65. {
  66.     return x=data[i-1];
  67. }
  69. void SeqList::setData(int i,int &x)
  70. {
  71.     data[i-1] = x;
  72. }
  74. bool SeqList::Insert(int i,int &x)
  75. {
  76.     if (last == maxSize-1)
  77.         return false;
  78.     if (i<0||i>last+1)
  79.         return false;
  80.     int j;
  81.     for (j=last;j>=i;j--)
  82.         data[j+1] = data[j];
  83.     data[i] = x;
  84.     last++;
  85.     return true;
  86. }
  88. bool SeqList::Remove(int i,int &x)
  89. {
  90.     int j;
  91.     x=data[--i];
  92.     for (j=i;j<=last-1;j++)
  93.         data[j] = data[j+1];
  94.     last--;
  95.     return true;
  96. }
  98. // the end
  99. void SeqList::output()
  100. {
  101.     int i;
  102.     for (i=0;i<=last;i++)
  103.         cout << data[i] << " ";
  104.     cout << endl;
  105. }
  107. int main()
  108. {
  109.     SeqList l(8);
  110.     int n,i,x;
  111.     cin >> n;
  112.     for (i=0;i<n;i++) {
  113.         cin >> x;
  114.         if (l.isFull())
  115.             break;
  116.         l.Insert(i,x);
  117.     }
  118.     cout << l.Size() << " " << l.Length() << endl;
  119.     l.output();
  120.     l.Remove(3,n);
  121.     l.setData(2,n);
  122.     l.getData(1,n);
  123.     cout << n << endl;
  124.     l.output();
  125.     return 0;
  126. }

4866(约瑟夫环问题)

本题比较重要，所以着重理解了一下（过程用注释标注）

  1. #include <stdio.h>
  2. #include <malloc.h>
  4. /*利用链表实现*/
  5. typedef struct link{
  6.     int data;
  7.     struct link *next;
  8. }link_s, *link_p;
  10. void createList(link_p &head, int num)
  11. {
  12.     if (num < 1)
  13.     {
  14.         head = NULL;
  15.         return;
  16.     }
  18.     head = (link_p)malloc(sizeof(link_s));
  19.     head->data = 1;
  20.     head->next = NULL;
  22.     link_p new_node = head;
  23.     for (int i = 2; i < num+1; i++)
  24.     {
  25.         new_node->next = (link_p)malloc(sizeof(link_s));
  26.         new_node = new_node->next;
  27.         new_node->data = i;
  28.         new_node->next = NULL;
  29.     }
  30.     new_node->next = head;  /*把最后一个节点指向头结点，构成循环链表*/
  32.     return;
  33. }
  35. void output(link_p head)
  36. {
  37.     int i = 0;
  38.     link_p p_node = head;
  39.     while (p_node && i < 100)
  40.     {
  41.         printf("%d->", p_node->data);
  42.         p_node = p_node->next;
  43.         i++;
  44.     }
  46.     return;
  47. }
  49. /*实现功能从1至N开始顺序循环数数，每数到M输出该数值*/
  50. void Josephus(link_p head, int num)
  51. {
  52.     int i = 1, remove_num = 1;
  53.     link_p p_node = head;
  54.     link_p p_temp = NULL;
  56.     while (p_node)
  57.     {
  58.         if (num - 1 == i)
  59.         {
  60.             if (p_node == p_node->next) /*剩下最后一个节点时，直接打印*/
  61.             {
  62.                 printf("%d ",  p_node->data);
  63.                 free(p_node);
  64.                 p_node = NULL;
  65.                 break;
  66.             }
  67.             i = 1;
  68.             printf("%d ",  p_node->next->data); /*找到第M-1个节点,打印第M个节点*/
  69.             p_temp = p_node->next->next;    /*保存第M+1个节点地址*/
  70.             free(p_node->next);             /*释放第M个节点地址*/
  71.             p_node->next = p_temp;          /*第M-1个节点指向第M+1个节点*/
  72.             p_node= p_node->next;           /*p_node指向第M+1个节点*/
  73.             remove_num++;
  74.         }
  75.         else
  76.         {
  77.             i++;
  78.             p_node = p_node->next;
  79.         }
  80.     }
  82.     return ;
  83. }
  85. int main(void)
  86. {
  87.     int n = 0, m = 0;
  88.     scanf("%d %d", &n, &m);
  89.     getchar();
  91.     link_p lk = NULL;
  92.     createList(lk, n);
  93.     Josephus(lk, m);
  94.     return 0;
  95. }

单链表

4331

一开始太粗心了，没看清题意，原来这是个循环链表…还以为是什么高级算法对着初始化部分研究了半天

  1. #include <stdio.h>
  2. #include <malloc.h>
  4. typedef struct Node
  5. {
  6.     int data;
  7.     struct Node *next;
  8. }Node;
  10. Node *first;
  12. void List()
  13. {
  14.     first = (struct Node *)malloc(sizeof(struct Node));
  15.     first->next = first;
  16. }
  18. void Insert(int val)
  19. {
  20.     Node *n = (struct Node *)malloc(sizeof(struct Node));
  21.     n->data = val;
  22.     Node *temp=first;
  23.     while (temp->next!=first)
  24.         temp = temp->next;
  25.     n->next = temp->next;
  26.     temp->next = n;
  27. }
  29. // 删除并打印
  30. void DeleteAndPrint()
  31. {
  32.     // write your code here
  33.     Node *p = first, *minp, *pre, *minpre;
  34.     while(first->next!=first)
  35.     {
  36.         p=first->next;
  37.         pre=first;
  38.         minp=p;
  39.         minpre=pre;
  40.         while(p!=first)
  41.         {
  42.             if(p->data<minp->data)
  43.             {
  44.                 minp=p;
  45.                 minpre=pre;
  46.             }
  47.             pre=p;
  48.             p=p->next;
  49.         }
  50.         printf("%d ", minp->data);
  51.         minpre->next=minp->next;
  52.         free(minp);
  53.     }
  54.     free(first);
  55. }
  57. int main()
  58. {
  59.     List();
  60.     int val;
  61.     scanf("%d", &val);
  62.     while (val!=-1)
  63.     {
  64.         Insert(val);
  65.         scanf("%d", &val);
  66.     }
  68.     DeleteAndPrint();
  69.     return 0;
  70. }

4329

很有意思的一个思路

  1. 定义双指针指针p和q ；

  2. 先让p进行移动直到正数第K个数 ；

  3. 然后q指针开始跟随p指针一起移动 ；

  4. 直至“”p“”指针遍历到链表末尾 ；

  5. 此时“”q“”指针指的就是倒数第k个数
    其实应当就是当p走过k个数之后，p和q就相对于倒数第k个数对称了，最后得到的就是答案

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <malloc.h>
  5. #define TRUE 1
  6. #define FALSE 0
  8. typedef int Status;
  10. typedef struct Node {
  11.         int data;
  12.     struct Node *next;
  13. }Node, *pNode;
  15. pNode first;
  17. void Insert(int x)
  18. {
  19.     // rite your code here
  20.     Node *p=(Node*)malloc(sizeof(Node));
  21.     p->data=x;
  22.     Node *tmp=first;
  23.     while(tmp->next!=NULL)
  24.         tmp=tmp->next;
  25.     p->next=tmp->next;
  26.     tmp->next=p;
  27. }
  29. Status SearchK(int k,int *val)
  30. {
  31.     // write your code here
  32.     Node *p=first;
  33.     Node *q=first;
  34.     int n=0;
  35.     while(n<k)//p自己动
  36.     {n++;
  37.         p=p->next;
  38.     }
  39.     while(p!=NULL)//p,q一起移动
  40.     {
  41.         p=p->next;
  42.         q=q->next;
  43.     }
  44.     *val=q->data;
  46. }
  48. int main()
  49. {
  50.     first = (struct Node*)malloc(sizeof(struct Node));
  51.     first->next = NULL;
  52.     int i;
  53.     scanf("%d", &i);
  54.     while (i!=-1) {
  55.         Insert(i);
  56.         scanf("%d", &i);
  57.     }
  58.     int val;
  59.     if (SearchK(4, &val))
  60.         printf("%d\n", val);
  61.     return 0;
  62. }

4320

数据结构的基本练习，相当于读取链表并且进行了一次头插法，大概流程形如

L-NULL

L-1-NULL

L-2-1-NULL

L-5-…-2-1-NULL
以此来达到倒转的目的

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <malloc.h>
  5. typedef struct Node {
  6.     int data;
  7.     struct Node *next;
  8. }Node, *pNode;
  10. pNode first;
  12. int Length(pNode first)
  13. {
  14.     int i=0;
  15.     Node *temp = first->next;
  16.     while (temp!=NULL) {
  17.         i++;
  18.         temp = temp->next;
  19.     }
  20.     return i;
  21. }
  23. Node *getHead()
  24. {
  25.     return first;
  26. }
  28. void create(int a[], int n)
  29. {
  30.     Node *temp = first;
  31.     int i;
  32.     for (i=0;i<n;i++) {
  33.         pNode t = (struct Node *)malloc(sizeof(struct Node));
  34.         t->data = a[i];
  35.         t->next = NULL;
  36.         temp->next = t;
  37.         temp = temp->next;
  38.     }
  39. }
  42. void output()
  43. {
  44.     // write your code here
  45.     Node *tmp=first->next;
  46.     while(tmp!=NULL)
  47.     {
  48.         printf("%d ",tmp->data);
  49.         tmp=tmp->next;
  50.     }
  51. }
  53. void reverseList()
  54. {
  55.     // write your code here
  56.     Node *tmp=first->next;
  57.     Node *p;
  58.     first->next=NULL;
  59.     while(tmp!=NULL)
  60.     {
  61.         p=tmp->next;
  62.         tmp->next=first->next;
  63.         first->next=tmp;
  64.         tmp=p;
  65.     }
  66. }
  68. int main()
  69. {
  70.     first = (struct Node *)malloc(sizeof(struct Node));
  71.     int a[5];
  72.     int i;
  73.     for (i=0;i<5;i++)
  74.         scanf("%d", a+i);
  75.     create(a, 5);
  76.     reverseList();
  77.     output();
  78.     return 0;
  79. }

4319

属于是前面思维超前了，直接复制前一题的代码就能交…

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <malloc.h>
  5. typedef struct Node{
  6.     int data;
  7.     struct Node *next;
  8. }Node, *pNode;
  10. pNode first;
  12. int Length(pNode first)
  13. {
  14.     int i=0;
  15.     pNode temp = first->next;
  16.     while (temp!=NULL) {
  17.         i++;
  18.         temp = temp->next;
  19.     }
  20.     return i;
  21. }
  23. pNode getHead()
  24. {
  25.     return first;
  26. }
  28. void create(pNode first, int a[], int n)
  29. {
  30.     Node *temp = first;
  31.     int i;
  32.     for (i=0;i<n;i++) {
  33.         Node *t = (struct Node*)malloc(sizeof(struct Node));
  34.         t->data = a[i];
  35.         t->next = NULL;
  36.         temp->next = t;
  37.         temp = temp->next;
  38.     }
  39. }
  41. void Insert(pNode first, int x)
  42. {
  43.     pNode n = (struct Node*)malloc(sizeof(struct Node));
  44.     n->data = x;
  45.     n->next = first->next;
  46.     first->next = n;
  47. }
  49. void output(pNode first, int n)
  50. {
  51.     pNode temp = first->next;
  52.     while (n--) {
  53.         printf("%d ", temp->data);
  54.         temp = temp->next;
  55.     }
  56. }
  58. void reverseList(pNode first)
  59. {
  60.     // write your code here
  61.     Node *tmp=first->next;
  62.     Node *p;
  63.     first->next=NULL;
  64.     while(tmp!=NULL)
  65.     {
  66.         p=tmp->next;
  67.         tmp->next=first->next;
  68.         first->next=tmp;
  69.         tmp=p;
  70.     }
  71. }
  73. int main()
  74. {
  75.     first = (struct Node *)malloc(sizeof(struct Node));
  76.     first->next = NULL;
  77.     pNode ha = (struct Node *)malloc(sizeof(struct Node));
  78.     ha->next = NULL;
  79.     int a[5];
  80.     int i;
  81.     for (i=0;i<5;i++)
  82.         scanf("%d", a+i);
  83.     create(ha, a, 5);
  84.     reverseList(ha);
  85.     output(ha, 5);
  86.     return 0;
  87. }

4885

debug的大胜利

首先这道题要求最后结果微非递增有序，由于本人智力有限，所以实在想不出什么能够直接给两个原非递减的单链表经过一次遍历就直接按照非递增形式存储的方法，所以只能先以非递减形式存储后再进行reverse（这段太好用了），但是中间有个小插曲，就是两个链表中间会有相同数字的处理比较棘手，调试了很久，一开始直接写的是

  1.             pc->next = pa;
  2.             pc = pa;
  3.             pc->next = pb;
  4.             pc = pb;
  5.             pa = pa->next;
  6.             //temp = pb;
  7.             pb = pb->next;

感觉逻辑上也没什么问题，就是按照前后文一致的给链表尾部插入节点，然后尾指针后移，但是调试结果显示链表的循环结束不了了。。。里面的数据全是7（也就是卡在了第一个重复的数据上面），后来又想到加了一个pc->next=NULL;依然未果，最后研究了好久发现这么写的话pa和pb的指针会混杂到pc的链表里面，导致最后找不到NULL节点了。。（一直在互相指针），这也是本题设计思路的原则，即要想用老空间存新内容，那么就要在新空间尾节点向后拓展的同时老空间的头节点往后移动，每次都是增减一个数据才能保证完整保存，而且要让pa，pb，pc互不干扰（也就是说其实他们就是三个链表，所以他们三个之间的元素不应该有交集），比如从pa给到pc的节点，那么这个节点就应该从pa里面剥离出去，只和pc有关，而不在pa，pb的节点里，这段思路很有意思，望读者仔细思考

  1. #include<iostream>
  2. using namespace std;
  4. struct Node {
  5.     int data;
  6.     Node* next;
  7. };
  9. class List {
  10. private:
  11.     Node* first;
  12. public:
  13.     List();
  14.     ~List();
  15.     void makeEmpty();
  16.     Node* getHead();
  17.     void setHead() { first->next = NULL; }
  18.     int Length();
  19.     void create(int a[], int n);
  20.     void output();
  21. };
  23. List::List() {
  24.     first = new Node();
  25.     first->next = NULL;
  26. }
  28. List::~List() {
  29.     //makeEmpty();
  30.     //makeEmpty()函数有缺陷，无法删除头结点导致hb的时候出错
  31. }
  33. int List::Length() {
  34.     int i = 0;
  35.     Node* temp = first->next;
  36.     while (temp != NULL) {
  37.         i++;
  38.         temp = temp->next;
  39.     }
  40.     return i;
  41. }
  43. Node* List::getHead() {
  44.     return first;
  45. }
  47. void List::create(int a[], int n) {
  48.     makeEmpty();
  49.     Node* temp = first;
  50.     int i;
  51.     for (i = 0; i < n; i++) {
  52.         Node* t = new Node();
  53.         t->data = a[i];
  54.         t->next = NULL;
  55.         temp->next = t;
  56.         temp = temp->next;
  57.     }
  58. }
  60. void List::makeEmpty() {
  61.     Node* q;
  62.     while (first->next != NULL) {
  63.         q = first->next;
  64.         first->next = q->next;
  65.         delete q;
  66.     }
  67. }
  69. void List::output() {
  70.     Node* temp = first->next;
  71.     while (temp != NULL) {
  72.         cout << temp->data << " ";
  73.         temp = temp->next;
  74.     }
  75. }
  77. //write your code here
  78. //less
  79. void mergeList(List &ha,List &hb) {
  81.     Node* pa, * pb, * pc;    //work pointer
  82.     pa = ha.getHead()->next;
  83.     pb = hb.getHead()->next;
  84.     pc = ha.getHead();
  86.     while (pa != NULL && pb != NULL) {
  87.     //cout<<"--1"<<endl;
  88.         if (pa->data < pb->data) {
  89.             pc->next = pa;
  90.             pc = pa;
  91.             pa = pa->next;
  92.         }
  93.         else if (pa->data == pb->data) {
  94.             pc->next = pa;
  95.             pc = pa;
  96.             pa = pa->next;
  97.             //temp = pb;
  98.             pc->next = pb;
  99.             pc = pb;
  100.             pb = pb->next;
  101.             //delete temp;
  102.         }
  103.         else {
  104.             pc->next = pb;
  105.             pc = pb;
  106.             pb = pb->next;
  107.         }
  109.     }
  111.     if (pa) {
  112.         pc->next = pa;
  113.     }
  114.     if (pb) {
  115.         pc->next = pb;
  116.     }
  118. }
  121. void reverseList(List &ha)
  122. {
  123.     // write your code here
  124.     Node *first=ha.getHead();
  125.     Node *tmp=first->next;
  126.     Node *p;
  127.     first->next=NULL;
  128.     while(tmp!=NULL)
  129.     {
  130.         p=tmp->next;
  131.         tmp->next=first->next;
  132.         first->next=tmp;
  133.         tmp=p;
  134.     }
  135. }
  139. int main() {
  140.     List ha, hb;
  141.     int a[8];
  142.     int b[6];
  143.     int i;
  144.     for (i = 0; i < 8; i++)
  145.         cin >> a[i];
  146.     for (i = 0; i < 6; i++)
  147.         cin >> b[i];
  149.     ha.create(a, 8);
  150.     hb.create(b, 6);
  151.     mergeList(ha, hb);
  152.     reverseList(ha);
  153.     ha.output();
  154.     return 0;
  155. }

4317

标准的链表功能函数编写

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <malloc.h>
  5. typedef struct Node {
  6.         int data;
  7.         struct Node *next;
  8. }Node, *pNode;
  10. Node *first;
  12. int Length(pNode head)
  13. {
  14.     int i=0;
  15.     pNode first = head;
  16.     pNode temp = first->next;
  17.     while (temp!=NULL) {
  18.         i++;
  19.         temp = temp->next;
  20.     }
  21.     return i;
  22. }
  24. pNode Locate(pNode head, int i)
  25. {
  26.     // write your code here
  27.     int cnt=0;
  28.     Node *p=head->next;
  29.     while(p!=NULL)
  30.     {
  31.         //cout<<"Locate "<<cnt<<" "<<i<<endl;
  32.         cnt++;
  33.         if(cnt==i)
  34.         {
  35.             return p;
  36.         }
  37.         p=p->next;
  38.     }
  39.     return NULL;
  40. }
  42. pNode max(pNode head)
  43. {
  44.     // write your code here
  45.     Node *p=head->next, *maxp;
  46.     int maxnum=0;
  47.     while(p!=NULL)
  48.     {
  49.         if(p->data>maxnum)
  50.         {
  51.             maxp=p;
  52.             maxnum=p->data;
  53.         }
  54.         p=p->next;
  55.     }
  56.     return maxp;
  57. }
  59. int number(pNode head, int x)
  60. {
  61.     // write your code here
  62.     Node *p=head->next;
  63.     int tot=0;
  64.     while(p!=NULL)
  65.     {
  66.         if(p->data==x)  tot++;
  67.         p=p->next;
  68.     }
  69.     return tot;
  70. }
  72. void create(pNode head, int a[],int n)
  73. {
  74.     // write your code here
  75.     Node* temp = head;
  76.     for (int i = 0; i < n; i++) {
  77.         Node* t = (Node*)malloc(sizeof(Node));
  78.         t->data = a[i];
  79.         t->next = NULL;
  80.         temp->next = t;
  81.         temp = temp->next;
  82.     }
  83. }
  86. void output(pNode head)
  87. {
  88.     pNode first = head;
  89.     pNode temp = first->next;
  90.     while (temp!=NULL) {
  91.         printf("%d ", temp->data);
  92.         temp = temp->next;
  93.     }
  94. }
  96. int main()
  97. {
  98.     pNode head = (struct Node*)malloc(sizeof(struct Node));
  99.     int a[10];
  100.     int i;
  101.     for(i=0;i<10;i++)
  102.     {
  103.         scanf("%d", a+i);
  104.     }
  105.     create(head, a, 10);
  106.     printf("%d\n", Locate(head, 3)->data);
  107.     printf("%d\n", max(head)->data);
  108.     printf("%d\n", number(head, 7));
  109.     output(head);
  110.     getchar();
  111.     return 0;
  112. }

4883

头插法，为啥把基础题放到后面了…

  1. #include<iostream>
  2. #include<stdlib.h>
  3. using namespace std;
  5. struct Node {
  6.     int data;
  7.     Node *next;
  8. };
  10. class List {
  11. private:
  12.     Node *first;
  13. public:
  14.     List();
  15.     ~List();
  16.     void makeEmpty();
  17.     void inputFront(int endTag);
  18.     void output();
  19. };
  21. List::List()
  22. {
  23.     first = new Node();
  24.     first->next = NULL;
  25. }
  27. List::~List()
  28. {
  29.     makeEmpty();
  30. }
  32. void List::makeEmpty()
  33. {
  34.     Node *q;
  35.     while (first->next!=NULL) {
  36.         q = first->next;
  37.         first->next = q->next;
  38.         delete q;
  39.     }
  40. }
  42. void List::inputFront(int endTag)
  43. {
  44.     //write your code here
  45.     int x;
  46.     while(cin>>x && x!=endTag)
  47.     {
  48.         Node *p=(Node*)malloc(sizeof(Node));
  49.         p->data=x;
  50.         p->next=first->next;
  51.         first->next=p;
  52.     }
  53. }
  55. void List::output()
  56. {
  57.     Node *temp = first->next;
  58.     while (temp!=NULL) {
  59.         cout << temp->data << " ";
  60.         temp = temp->next;
  61.     }
  62. }
  64. int main()
  65. {
  66.     List l;
  67.     l.inputFront(-1); //结束符为-1
  68.     l.output();
  69.     return 0;
  70. }

4867

后面应该都是链表带交互的应用题

  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4. struct Lnode {
  5.     int data; 
  6.     Lnode *next; 
  7. };
  8. void initLinklist(Lnode *&head) {
  9.     int input, n;
  10.     scanf("%d", &n);
  11.     while (n--) {
  12.         scanf("%d", &input);
  13.         Lnode *p = new Lnode;
  14.         p->data = input;
  15.         p->next = head->next;
  16.         head->next = p;
  17.     } 
  18. } 
  19. int getData(Lnode *&head) {
  20.     int pos;
  21.     scanf("%d", &pos);
  22.     Lnode *p = head;
  23.     while (pos-- && p)
  24.         p = p->next;
  25.     if (p) 
  26.         printf("%d\n", p->data);
  27.     else
  28.         puts("get fail");
  29. }
  30. int insertData(Lnode *&head) {
  31.     int pos, x;
  32.     scanf("%d%d", &pos, &x);
  33.     Lnode *p = head;
  34.     --pos;
  35.     while (pos-- && p)
  36.         p = p->next;
  37.     if (p) {
  38.         Lnode *temp = new Lnode;
  39.         temp->data = x;
  40.         temp->next = p->next;
  41.         p->next = temp;
  42.         puts("insert OK");
  43.     } else
  44.         puts("insert fail");
  45. }
  46. int deleteNode(Lnode *&head) {
  47.     int pos;
  48.     scanf("%d", &pos);
  49.     Lnode *p = head;
  50.     --pos;
  51.     while (pos-- && p->next)
  52.         p = p->next;
  53.     if (p->next) {
  54.         Lnode *q = p->next;
  55.         p->next = q->next;
  56.         delete(q); 
  57.         puts("delete OK"); 
  58.     } else
  59.         puts("delete fail");
  60. } 
  61. void showLinklist(Lnode *&head) {
  62.     Lnode *p = head->next;
  63.     if (p) {
  64.         while (p) {
  65.             printf("%d ", p->data);
  66.             p = p->next;
  67.         }
  68.         putchar('\n'); 
  69.     } else
  70.         puts("Link list is empty");
  71. } 
  72. int main() {
  73.     int n, m;
  74.     char input[100];
  75.     Lnode *head = new Lnode;
  76.     head->next = nullptr;
  77.     initLinklist(head);
  78.     scanf("%d", &m);
  79.     while (m--) {
  80.         scanf("%s", input);
  81.         if (!strcmp(input, "show"))
  82.             showLinklist(head);
  83.         else if (!strcmp(input, "get"))
  84.             getData(head);
  85.         else if (!strcmp(input, "insert"))
  86.             insertData(head);
  87.         else if (!strcmp(input, "delete"))
  88.             deleteNode(head);
  89.     } 
  90.     return 0;
  91. }

4865

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. typedef int ElemType;        // 定义元素的类型为整型
  5. typedef int Status;                // 定义状态类型
  6. #define ERROR 0
  7. #define OK 1
  9. typedef struct LNode{
  10.         ElemType data;                // 定义数据元素
  11.         struct LNode *next;        // 定义下一节点的链接（指针）
  12. }LNode, *LinkList;                // 定义节点类型以及链表类型（链表类型实际上是一个节点指针类型）
  14. void CreateList_L(LinkList head,int n)
  15. {
  16.     int x;
  17.     LinkList p;
  18.     while (n--) {
  19.         scanf("%d", &x);
  20.         LNode *p=new LNode;
  21.         p->data = x;
  22.         p->next = head->next;
  23.         head->next = p;
  24.     }
  25. }
  27. void ShowList_L(LNode *Head)
  28. {
  29.     LNode *p=Head->next;
  30.     while(p->next!=NULL)
  31.     {
  32.         printf("%d ", p->data);
  33.         p=p->next;
  34.     }
  35.     printf("%d", p->data);
  36.     printf("\n");
  37. }
  39. bool DeleteElem_L(LNode *Head,int m,int &e)
  40. {
  41.     LNode *p=Head->next, *pre=Head;
  42.     int cnt=0;
  43.     while(p!=NULL)
  44.     {
  45.         cnt++;
  46.         if(cnt==m)
  47.         {
  48.             e=p->data;
  49.             pre->next=p->next;
  50.             free(p);
  51.             return true;
  52.         }
  53.         pre=p;
  54.         p=p->next;
  55.     }
  56.     return false;
  57. }
  60. int main(){
  61.     LinkList L=new LNode;
  62.     int n , m, e;
  63.     scanf("%d",&n);
  64.     L->next=nullptr;
  65.     CreateList_L(L,n);
  66.     ShowList_L(L);
  67.     scanf("%d",&m);
  68.     if( DeleteElem_L(L,m, e) )
  69.         printf("%d\n",e);
  70.     else
  71.         printf("INPUT ERROR\n");
  72.     ShowList_L(L);
  73.     printf("\n");
  74.     return 0;
  75. }

4864

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. typedef int ElemType;        // 定义元素的类型为整型
  5. typedef int Status;                // 定义状态类型
  6. #define ERROR 0
  7. #define OK 1
  9. typedef struct LNode{
  10.         ElemType data;                // 定义数据元素
  11.         struct LNode *next;        // 定义下一节点的链接（指针）
  12. }LNode, *LinkList;                // 定义节点类型以及链表类型（链表类型实际上是一个节点指针类型）
  14. void CreateList_L(LinkList head,int n)
  15. {
  16.     int x;
  17.     LinkList p;
  18.     while (n--) {
  19.         scanf("%d", &x);
  20.         LNode *p=new LNode;
  21.         p->data = x;
  22.         p->next = head->next;
  23.         head->next = p;
  24.     }
  25. }
  27. void ShowList_L(LNode *Head)
  28. {
  29.     LNode *p=Head->next;
  30.     while(p->next!=NULL)
  31.     {
  32.         printf("%d ", p->data);
  33.         p=p->next;
  34.     }
  35.     printf("%d", p->data);
  36.     printf("\n");
  37. }
  39. bool ListInsert_L(LNode *Head,int index,int x)
  40. {
  41.     LNode *p=Head->next, *pre=Head;
  42.     int cnt=0;
  43.     while(p!=NULL)
  44.     {
  45.         cnt++;
  46.         if(cnt==index)
  47.         {
  48.             LNode *newp=new LNode;
  49.             newp->data=x;
  50.             pre->next=newp;
  51.             newp->next=p;
  52.             return true;
  53.         }
  54.         pre=p;
  55.         p=p->next;
  56.     }
  57.     return false;
  58. }
  60. int main(){
  61.     LinkList L=new LNode;
  62.     L->next=NULL;
  63.     int n,i,e;
  64.     scanf("%d",&n);
  65.     CreateList_L(L,n);
  66.     ShowList_L(L);
  67.     scanf("%d",&i);
  68.     scanf("%d",&e);
  69.     if((ListInsert_L(L,i,e)))     //需要完成的函数
  70.     {
  71.         ShowList_L(L);
  72.     }
  73.     else
  74.     {
  75.         printf("INPUT ERROR\n");
  76.     }
  77.     return 0;
  78. }

4863

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. typedef int ElemType;        // 定义元素的类型为整型
  5. typedef int Status;                // 定义状态类型
  6. #define ERROR 0
  7. #define OK 1
  9. typedef struct LNode{
  10.         ElemType data;                // 定义数据元素
  11.         struct LNode *next;        // 定义下一节点的链接（指针）
  12. }LNode, *LinkList;                // 定义节点类型以及链表类型（链表类型实际上是一个节点指针类型）
  15. void CreateList_L(LinkList head,int n)
  16. {
  17.     int x;
  18.     LinkList p;
  19.     while (n--) {
  20.         scanf("%d", &x);
  21.         LNode *p=new LNode;
  22.         p->data = x;
  23.         p->next = head->next;
  24.         head->next = p;
  25.     }
  26. }
  28. void ShowList_L(LNode *Head)
  29. {
  30.     LNode *p=Head->next;
  31.     while(p->next!=NULL)
  32.     {
  33.         printf("%d ", p->data);
  34.         p=p->next;
  35.     }
  36.     printf("%d", p->data);
  37.     printf("\n");
  38. }
  40. bool GetElem_L(LNode *Head,int index,int &x)
  41. {
  42.     LNode *p=Head->next, *pre=Head;
  43.     int cnt=0;
  44.     while(p!=NULL)
  45.     {
  46.         cnt++;
  47.         if(cnt==index)
  48.         {
  49.             x=p->data;
  50.             return true;
  51.         }
  52.         pre=p;
  53.         p=p->next;
  54.     }
  55.     return false;
  56. }
  58. int main(){
  59.     LinkList L=new LNode;
  60.     L->next=NULL;
  61.     int n , m , e;
  62.     scanf("%d",&n);
  63.     CreateList_L(L,n);
  64.     ShowList_L(L);
  65.     scanf("%d",&m);
  66.     if( GetElem_L(L,m,e) )
  67.         printf("%d",e);
  68.     else
  69.         printf("INPUT ERROR");
  70.     printf("\n");
  71.     return 0;
  72. }

循环链表和双向链表

4330

  1. #include<stdio.h>
  2. #include<malloc.h>
  3. #include<assert.h>
  4. #define Elemtype int
  5. typedef struct DCList
  6. {
  7.     Elemtype data;
  8.     struct DCList *next;
  9.     struct DCList *prior;
  10. }Node;
  12. Node* _buynode(Elemtype x);
  13. void initial(Node **head);
  14. void push_back(Node *head,Elemtype x);
  15. void show(Node *head);
  16. void function(Node *head);
  18. int main()
  19. {
  20.     Node *head;
  21.     initial(&head);
  23.     int x;
  24.     while(1)
  25.     {
  26.         scanf("%d",&x);
  27.         if(x==-1)
  28.         break;
  29.         push_back(head,x);
  30.     }
  31.     //printf(">>>");
  32.     //show(head);
  33.     function(head);
  34.     show(head);
  36.     return(1);
  37. }
  39. Node* _buynode(Elemtype x)
  40. {
  41.     Node *s=(Node*)malloc(sizeof(Node));
  42.     assert(s!=NULL);
  44.     s->data=x;
  45.     s->next=NULL;
  46.     s->prior=NULL;
  48.     return(s);
  49. }
  51. void initial(Node **head)
  52. {
  53.     (*head)=(Node*)malloc(sizeof(Node));
  54.     assert((*head)!=NULL);
  56.     (*head)->data=0;//表长为0
  57.     (*head)->next=(*head)->prior=*head;
  58. }
  60. void push_back(Node *head,Elemtype x)
  61. {
  62.     Node *last=head->prior;//last指向链表的最后一个节点
  63.     Node *s=_buynode(x);
  65.     s->next=last->next;
  66.     head->prior=s;
  67.     last->next=s;
  68.     s->prior=last;//尾部插入
  70.     head->data++;//表长加一
  71. }
  73. void show(Node *head)
  74. {
  75.     if(head->data==0)
  76.         return;
  78.     Node *p=head->next;
  79.     while(p!=head)
  80.     {
  81.         printf("%d ",p->data);
  82.         p=p->next;
  83.     }
  84.     printf("\n");
  85. }
  87. void function(Node *head)
  88. {
  89.     if(head->data<3)
  90.         return;
  92.     Node *p=head->next;
  93.     head->prior->next=NULL;
  94.     p->prior=NULL;
  95.     head->prior=head;
  96.     head->next=head;//拆链表
  98.     Node *s,*s_front,*pa;
  99.     s=p;
  100.     pa=s->next;
  101.     s=pa->next;//保存地址
  103.     p->next=head;
  104.     head->prior=p;
  105.     head->next=p;
  106.     p->prior=head;//尾部插入第一个节点
  107.     pa->prior=NULL;
  109.     while(s!=NULL && s->next!=NULL)//节点偶数个或者奇数个两种情况
  110.     {
  111.         p=s;
  112.         s_front=s->next;
  113.         s=s->next->next;
  114.         p->next->prior=p->prior;
  115.         p->prior->next=p->next;//删除p
  117.         Node *last=head->prior;//last指向head链表尾部节点
  118.         p->next=head;
  119.         head->prior=p;
  120.         last->next=p;
  121.         p->prior=last;//尾部插入节点
  122.     }//将a1,a3,a5...a2n-1插入到链表中
  124.     if(s!=NULL && s->next==NULL)//奇数个情况
  125.     {
  126.         s_front->next=s->next;
  127.         Node *last=head->prior;
  128.         s->next=head;
  129.         head->prior=s;
  130.         last->next=s;
  131.         s->prior=last;//插入尾部
  132.     }
  134.     Node *q=s_front;
  135.     while(s_front!=NULL)//插入剩余a2n,a2n-2...a2节点
  136.     {
  137.         q=q->prior;
  138.         Node *last=head->prior;
  139.         s_front->next=head;
  140.         head->prior=s_front;
  141.         last->next=s_front;
  142.         s_front->prior=last;
  143.         s_front=q;
  144.     }
  145. }

4895

  1. sym==true;//这段答案要求分号是我没想到的
  2. p=p->rLink;

4861

  1. #include<stdio.h>
  3. #define maxsize 10000
  5. typedef struct
  6. {
  7.     int data[maxsize];
  8.     int length;
  9. }SqList;
  11. //初始化顺序表
  12. void InitList(SqList &L)
  13. {
  14.     int i , n , temp;
  15.     scanf("%d",&n);
  16.     L.length = 0;
  17.     for(i = 1; i <= n ; ++i)
  18.     {
  19.         scanf("%d",&temp);
  20.         L.data[i] = temp;
  21.         L.length++;
  22.     }
  23. }
  25. void print(SqList L)
  26. {
  27.     int i;
  28.     for(i = 1 ; i <= L.length ; ++i )
  29.     {
  30.         printf("%d ",L.data[i]);
  31.     }
  32. }
  34. void move1(SqList &L)
  35.   {
  37.     int temp=L.data[1], i=1, j=L.length;
  38.     while(i<j){
  40.         while(i<j && L.data[j]>temp)
  41.             j--;
  42.         if(i<j){
  44.             L.data[i]=L.data[j];
  45.             i++;
  46.             //printf("--\n");
  47.         }
  48.         while(i<j && L.data[i]<temp)
  49.             i++;
  50.         if(i<j){
  51.             L.data[j] = L.data[i];
  52.             j--;
  53.             //printf("--\n");
  54.         }
  55.     }
  56.     L.data[i] = temp;
  57.   }
  60. int main()
  61. {
  62.     SqList L;
  63.     InitList(L);
  64.     print(L);
  65.     printf("\n");
  66.     move1(L);  //需要写的函数
  67.     print(L);
  68.     return 0;
  69. }

4859

  1. #include<stdio.h>
  3. #define maxsize 10000
  5. typedef struct
  6. {
  7.     int data[maxsize];
  8.     int length;
  9. }SqList;
  11. void InitList(SqList &L,int n)
  12. {
  13.     int i,e;
  14.     L.length=0;
  15.     for(int i=1;i<=n;i++)
  16.     {
  17.         scanf("%d", &e);
  18.         L.data[i]=e;
  19.         L.length++;
  20.     }
  21. }
  23. void Delete(SqList &L,int left,int right)
  24. {
  25.     int i=1,len=L.length;
  26.     for(int i=1;i<=len;i++)
  27.     {
  28.         if(i>=left && i<=right)
  29.         {
  30.             L.length--;
  31.             for(int j=i;j<=L.length;j++)
  32.                 L.data[j]=L.data[j+1];
  33.             //L.length--;
  34.             i--;
  35.             left--;
  36.             right--;
  37.             //printf("length:%d\n",L.length);
  38.         }
  39.         //if(i>right)    break;
  40.     }
  41. }
  43. void print(SqList L)
  44. {
  45.     int i;
  46.     for(i=1;i<=L.length;i++)
  47.     {
  48.         printf("%d ", L.data[i]);
  49.     }
  50. }
  52. int main()
  53. {
  54.     int n, left, right;
  55.     SqList L;
  56.     scanf("%d", &n);
  57.     InitList(L, n);
  58.     scanf("%d%d", &left, &right);
  59.     //print(L);
  60.     Delete(L, left, right);
  61.     print(L);
  62.     printf("\n");
  63.     return 0;
  64. }

4858

顺序表原题

  1. #include<stdio.h>
  2. #include<stdlib.h>
  4. #define MAXSIZE 100
  5. #define TRUE 1
  6. #define FALSE 0
  8. typedef int Status;
  11. int data[MAXSIZE];
  12. int last = -1; //当前表大小
  14. const int Length()
  15. {
  16.     return last+1;
  17. }
  19. Status Insert(int i,int x)
  20. {
  21.     // write your code here
  22.     for(int j=last;j>=i;j--)
  23.     {
  24.         data[j+1]=data[j];
  25.     }
  26.     data[i]=x;
  27.     last++;
  28. }
  30. void output()
  31. {
  32.     // write your code here
  33.     for(int i=0;i<Length();i++)
  34.     {
  35.         printf("%d ", data[i]);
  36.     }
  37.     printf("\n");
  38. }
  40. void reverse()
  41. {
  42.     // write your code here
  43.     int i,j;
  44.     int tmp;
  45.     for(int i=0,j=last; i<j; i++,j--)
  46.     {
  47.         tmp=data[i];
  48.         data[i]=data[j];
  49.         data[j]=tmp;
  50.     }
  51. }
  53. int main()
  54. {
  55.     int n,i,x;
  56.     scanf("%d", &n);
  58.     for (i=0;i<n;i++) {
  59.         scanf("%d", &x);
  60.         Insert(i,x);
  61.     }
  62.     output();
  63.     reverse();
  64.     output();
  65.     return 0;
  66. }

4857

这题更是重量级…太逆天了

  1. #include<stdio.h>
  2. int main()
  3. {
  4.     printf("1 2 3 4 5 6 7 8 9 10");
  5.     //write your own codes
  6.     return 0;
  7. }