数据结构实验报告——线性表

顺序表

#include 
     using namespace std; const int LISTSIZE=10;///顺序存储的最大元素数量 const int maxn=100;///每次分配的元素个数 #define ERROR -1 #define OK 1 int n,m; typedef int ElemType; struct List { 
    ElemType* elem; int len,listsize; }; void output(List &L) ///遍历顺序表 { 
    for(int i=0; i<L.len; i++) { 
    cout<<L.elem[i]; if(i==L.len-1) puts(""); else cout<<" "; } } void initlist(List &L) { 
    L.elem=(ElemType*)malloc(LISTSIZE*sizeof(ElemType)); if(!L.elem) exit(ERROR);///内存分配失败 L.len=0;///当前存储的元素个数 L.listsize=LISTSIZE; } int insertlist(List &L,int pos,ElemType e) { 
    if(pos<1||pos>L.len+1) return 0;///插入位置不合法 if(L.len>=L.listsize) ///当前元素的个数大于最大个数 需要申请空间 { 
    ElemType* newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTSIZE)*sizeof(ElemType)); if(!newbase) return ERROR; L.elem=newbase; L.listsize+=LISTSIZE; } ElemType *q=&(L.elem[pos-1]); ElemType *p=&(L.elem[L.len-1]); while(p>=q) { 
    *(p+1)=*p; p--; } *q=e; L.len++; return 1; } string Find(List &L,ElemType e,int &pos) { 
    for(int i=0; i<L.len; i++) if(L.elem[i]==e) { 
    pos=i; return "YES"; } return "NO"; } string Del(List &L,ElemType e) { 
    int pos; if(Find(L,e,pos)=="NO") return "Del Error!"; cout<<L.len<<endl; ElemType *p=&(L.elem[pos]); ElemType *q=&(L.elem[L.len-2]); while(p<=q){ 
    *p=*(p+1);p++; } L.len--; return "Del Success!"; } void Union(List &L1,List &L2,List &L){ 
   ///递增合成递增的 int i=L1.len-1,j=L2.len-1,t=0; while(i>=0&&j>=0){ 
    t++; if(L1.elem[i]>L2.elem[j]){ 
    insertlist(L,t,L1.elem[i]); i--; } else{ 
    insertlist(L,t,L2.elem[j]); j--; } } while(i>=0){ 
    t++; insertlist(L,t,L1.elem[i]); i--; } while(j>=0){ 
    t++; insertlist(L,t,L2.elem[j]); j--; } } int main() { 
    /*List L; initlist(L); int n; cin>>n; for(int i=1; i<=n; i++) { int x; cin>>x; insertlist(L,i,x); } output(L); for(int i=1; i<=2; i++) { cout<<"请输入您想要查找的元素"< 
   
     >x; if(Find(L,x,pos)=="YES") { printf("查找成功，您想要查找的元素位置为%d\n",pos); } else printf("查找失败！\n"); } for(int i=1; i<=10; i++) { cout<<"请输入您想要删除的元素"< 
    
      >x; if(Del(L,x)=="Del Success!") { printf("删除成功，删除后的序列为\n"); output(L); } else printf("删除失败！\n"); }*/ 
     
    List L1,L2,L; ///初始化 initlist(L1); initlist(L2); initlist(L); cout<<"请输入表A的元素个数：\n"<<endl; cin>>n; cout<<"请输入表A的元素：\n"<<endl; for(int i=1;i<=n;i++){ 
    int x;cin>>x; insertlist(L1,i,x); } cout<<"请输入表B的元素个数：\n"<<endl; cin>>m; cout<<"请输入表B的元素：\n"<<endl; for(int i=1;i<=m;i++){ 
    int x;cin>>x; insertlist(L2,i,x); } Union(L1,L2,L); cout<<"合并后的表C的元素为：\n"<<endl; output(L); return 0; } 

链表

#include 
     using namespace std; /* （2）单链表的操作 ① 输入一组整型元素序列，使用尾插法建立一个带有头结点的单链表。 ② 实现该线性表的遍历。 ③ 实现单链表的就地逆置。 ④ 建立两个按值递增有序的单链表，将他们合并成一个按值递增有序的单链表。 要求利用原来的存储空间，并且新表中没有相同的元素。 */ typedef int ElemType; typedef struct LNode{ 
    ElemType data; struct LNode *next; }Lnode,*LinkList; void initlist(LinkList &L){ 
   ///尾插法建立链表 LinkList p,t; int x;cin>>x; L=t=(LinkList)malloc(sizeof(LNode)); while(x){ 
    p=(LinkList)malloc(sizeof(LNode)); p->data=x; t->next=p; t=p; cin>>x; } t->next=NULL; } void visit(LinkList p){ 
   ///访问 cout<<p->data<<" "; } void output(LinkList L){ 
   ///遍历 LinkList p=L->next; while(p!=NULL){ 
    visit(p); p=p->next; } puts(""); } void Reverse(LinkList &L){ 
    LinkList p,q; p=L->next;L->next=NULL; while(p!=NULL){ 
    q=p->next; p->next=L->next; L->next=p; p=q; } } void Union(LinkList &La,LinkList Lb){ 
    LinkList pa,pb; pa=La->next,pb=Lb->next; free(Lb); LinkList last=La; while(pa&&pb){ 
    if(pa->data<pb->data){ 
    LinkList p=pa->next; pa->next=NULL; last->next=pa; last=last->next; pa=p; } else if(pa->data==pb->data){ 
    LinkList p=pa->next; pa->next=NULL; last->next=pa; last=last->next; pa=p; LinkList q=pb; pb=pb->next; free(q); } else{ 
    LinkList p=pb->next; pb->next=NULL; last->next=pb; last=last->next; pb=p; } } last->next=pa?pa:pb; } int main(){ 
    LinkList La; initlist(La); output(La); // Reverse(La); // output(La); LinkList Lb; initlist(Lb); Union(La,Lb); output(La); return 0; }