网站上线测试/重庆森林经典台词罐头

实验1

1顺序表的操作

① 随机产生一组2位整数，建立线性表的顺序存储结构，要求表中元素互不相同。

② 实现该线性表的遍历。

③ 在该顺序表中查找某一元素,查找成功显示查找元素，否则显示查找失败。

④ 在该顺序表中删除或插入指定元素。

⑤ 建立两个按值递增有序的顺序表，将他们合并成一个按值递减有序的顺序表。

2单链表的操作

① 输入一组整型元素序列，使用尾插法建立一个带有头结点的单链表。

② 实现该线性表的遍历。

③ 实现单链表的就地逆置。

④ 建立两个按值递增有序的单链表，将他们合并成一个按值递增有序的单链表。要求利用原来的存储空间，并且新表中没有相同的元素。

代码

1，少部分用了c++引用

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
struct List{int *list;int size;int len;
};
void swap(int &a,int &b)
{int t = a;a = b,b = t;
}
void init(List &list,int size,int len)
{list.list = (int*)malloc(sizeof(int)*size);///申请空间list.size = size;list.len = len;int vis[101] = {0};///标记数组for(int i=0;i<len;i++){int x = rand()%90+10;if(vis[x]){i--;continue;}list.list[i] = x;vis[x] = 1;}
}
int insert(List &list,int val,int pos)
{if(pos<0||pos>=list.len)return -1;if(list.len == list.size)///原空间不足，申请二倍list.list = (int*) realloc(list.list,sizeof(list)*2*list.size),list.size*=2;for(int i=list.len-1;i>=pos;i--)list.list[i+1] = list.list[i];list.list[pos] = val;list.len++;return 1;
}
int search(List list,int x)
{for(int i=0;i<list.len;i++)if(list.list[i] == x)return i;return -1;
}
int Delete(List &list,int pos)
{if(pos<0||pos>=list.len)return -1;for(int i=pos;i<list.len;i++)list.list[i] = list.list[i+1];list.len--;return 1;
}
void Merge(List list1,List list2,List &list3)
{list3.len = list1.len+list2.len;int i,j,k;i = 0,j = 0,k = list1.len+list2.len-1;for(int l = 0,r = 0;l<list1.len&&r<list2.len;)///去重{if(list1.list[l]==list2.list[r])k--,l++,r++,list3.len--;else if(list1.list[l]>list2.list[r])r++;elsel++;}while(i<list1.len && j<list2.len && k+1)///倒着扫一遍{if(list1.list[i]==list2.list[j]){list3.list[k--] = list1.list[i];i++,j++;}else if(list1.list[i]>list2.list[j])list3.list[k--] = list2.list[j++];elselist3.list[k--] = list1.list[i++];}while(i<list1.len)list3.list[k--] = list1.list[i++];while(j<list2.len)list3.list[k--] = list2.list[j++];
}
void Sort(List &list)///冒泡排序
{for(int i=0;i<list.len;i++)for(int j=i+1;j<list.len;j++)if(list.list[i]>list.list[j])swap(list.list[i],list.list[j]);
}
void Bianli(List list)
{for(int i=0;i<list.len;i++)printf("%d ",list.list[i]);printf("\n");
}
int main()
{srand(time(0));List lis1,lis2,lis3;init(lis1,100,3),init(lis2,100,3);init(lis3,100,0);Sort(lis1),Sort(lis2);for(int i=0;i<lis1.len;i++)printf("list1:%d\tlist2:%d\n",lis1.list[i],lis2.list[i]);printf("----------------------------\n");Merge(lis1,lis2,lis3);for(int i=0;i<lis3.len;i++)printf("list3:%d---%d\n",i,lis3.list[i]);insert(lis3,1111,2);printf("----------------------------\n");for(int i=0;i<lis3.len;i++)printf("list3:%d---%d\n",i,lis3.list[i]);printf("----------------------------\n");Delete(lis3,2);for(int i=0;i<lis3.len;i++)printf("list3:%d---%d\n",i,lis3.list[i]);printf("%d\n",search(lis3,lis1.list[1]));Bianli(lis1);return 0;
}

2，c++类实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
class List{private:struct Lst{int data;Lst *next;}head,*tail;int len;public:List(){head.next = NULL;tail = &head;len = 0;}bool Listempty(){return !head.next;}int GetList(int x){if(x<0||x>len){printf("error\n");return -1;}int cnt = 0;Lst Find = head;while(cnt<x && Find.next){cnt++;Find = *Find.next;}return Find.data;}int GetListlen(){return len;}void Listinsert(int val,int pos){int cnt = 0;Lst *Find = &head;while(cnt<pos-1 && Find->next){cnt++;Find = Find->next;}Lst *p = new Lst;p->data = val;p->next = Find->next;Find->next = p;len++;}void ListInsert(int val){Lst *p = new Lst;p->data = val;p->next =  NULL;tail->next = p;tail = p;len++;}void ListDelete(int x){int cnt = 0;Lst *Find = &head;while(cnt<x-1 && Find->next){cnt++;Find = Find->next;}Lst *p = Find->next;Find->next = p->next;delete p;len--;}void Ergodic(){Lst *p = head.next;while(p){printf("%d ",p->data);p = p->next;}printf("\n");}void reverse(){///头插法恰好是反序的，所以拆掉当前链表的同时头插法建立一个新的即可Lst *p = head.next;Lst *fp = new Lst;Lst *ep;fp->next = NULL;while(p){ep = p->next;p->next = fp->next;fp->next = p;p = ep;}head.next = fp->next;delete fp;}friend void Merge(List &a,List &b);
};
void Merge(List &a,List &b){List::Lst *pa = a.head.next,*pb = b.head.next,*head,*tail,*del;b.len = 0;b.head.next = NULL;int len = 0;if(pa->data < pb->data)head = pa,pa = pa->next;elsehead = pb,pb = pb->next;tail = head;while(pa&&pb){if(pa->data==pb->data){if(pa->data!=tail->data)tail->next = pa,tail = pa,pa = pa->next,len++;elsepa = pa->next,pb = pb->next;}else if(pa->data < pb->data){tail->next = pa,tail = pa,pa = pa->next,len++;}elsetail->next = pb,tail = pb,pb = pb->next,len++;}while(pa)tail->next = pa,tail = pa,pa = pa->next,len++;while(pb)tail->next = pb,tail = pb,pb = pb->next,len++;tail->next = NULL;a.head.next = head;a.len = len;
}
int main()
{List a,b,c;c.ListInsert(5);c.ListInsert(4);c.ListInsert(3);a.ListInsert(1);a.ListInsert(7);a.ListInsert(9);int len = c.GetListlen();c.Ergodic();c.reverse();c.Ergodic();a.Ergodic();Merge(c,a);a.Ergodic();c.Ergodic();return 0;
}

实验2

1输入一个十进制数，利用栈操作，将该数转换成n进制数。

2输入一个表达式，表达式中包括三种括号“（）”、“[]”和“{}”，判断该表达式的括号是否匹配。

 

二合一，纯c语言

#include <stdio.h>
#include <stdlib.h>
#include <math.h>//Compiler version gcc 6.3.0
typedef union base{int _int;char _char;long l_int;long long ll_int;
}base;
typedef struct Stack{base *p;int *state;int size,len;
}Stack;
void init(Stack *x){(*x).p = (base*)malloc(sizeof(base)*30);(*x).state = (int*)malloc(sizeof(int)*30);(*x).size = 30,(*x).len = 0;
}
void top(base *e,int *s,Stack x){if(x.len)*e = x.p[x.len-1],*s = x.state[x.len-1];
}
void pop(Stack *x){if((*x).len)(*x).len--;
}
void push(base val,int s,Stack *x){if((*x).len==(*x).size){(*x).p = (base*)realloc((*x).p,(*x).size*sizeof(base)*2);(*x).state = (int*)realloc((*x).state,(*x).size*sizeof(int)*2);(*x).size *= 2;}(*x).p[(*x).len] = val;(*x).state[(*x).len] = s;(*x).len++;
}
int empty(Stack x){return !x.len;
}
void clear(Stack *x){(*x).len = 0;
}
void cout(base x,int s){switch (s){case 0:printf("%d",x._int);break;case 1:printf("%c",x._char);break;case 2:printf("%ld",x.l_int);break;case 3:printf("%lld",x.ll_int);}
}
void Changebase(){Stack A;init(&A);int n,R;while(~scanf("%d%d",&n,&R)){int tn = n;while(n){int y = n%R,s;base x;if(y<10)s = 0,x._int = y;else s = 1,x._char = y-10+'A';push(x,s,&A);n/=R;}printf("%d change to %d base is ",tn,R);while(!empty(A)){int s;base e;top(&e,&s,A);pop(&A);cout(e,s);}printf("\n");}
}
void check(){Stack A;init(&A);char a[1000];while(~scanf("%s",a)){int flag = 0;for(int i = 0; a[i] ; i++){if(a[i]=='('||a[i]=='['||a[i]=='{'){base x;x._char = a[i];push(x,1,&A);}else if(a[i]==')'||a[i]==']'||a[i]=='}'){base c;int s;if(empty(A)){flag = 1;break;}top(&c,&s,A);if(c._char=='{'&&a[i]=='}')pop(&A);else if(c._char=='('&&a[i]==')')pop(&A);else if(c._char=='['&&a[i]==']')pop(&A);elsebreak;}}printf("%s\n",(empty(A)&&!flag)?"Yes,match success!":"No,can't match!");clear(&A);}
}
int main()
{///Changebase();check();return 0;
}