队列，栈和链表的C++实现

//链表的定义和各种操作 #include<iostream> using namespace std; typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; }LNode,*LinkList; //初始化一个链表 LinkList InitList() { LinkList L; L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; return L; } //创建一个含n个字符的链表(逆序） void CreateList(LinkList L,int n) { LinkList p; cout<<"请输入数据:"<<endl; for(int i=0;i<n;i++) { p=(LinkList)malloc(sizeof(LNode)); cin>>p->data; p->next =L->next; L->next=p; } } //将一个数据插入到链表的某一个位置 void InsertList(LinkList L,int index,ElemType e) { LinkList p; p=L; int j=0; //寻找第index-1个节点 while(p&&j<index-1) { p=p->next; ++j; } if(!p||j>index-1) return; LinkList n = (LinkList)malloc(sizeof(LNode)); n->data=e; n->next =p->next; p->next=n; } //判读链表是否为空表 bool ListEmpty(LinkList L) { bool flag=false; if(L->next ) flag = true; return flag; } //读取链表的长度 int ListLength(LinkList L) { int length=0; LinkList p = L; while(p->next) { length++; p=p->next; } return length; } //获取链表第i个位置的元素 ElemType GetElem(LinkList L,int index) { ElemType e; if(index>ListLength(L)||index<=0) return NULL; LinkList p=L->next; int j=1; while(j<index&&p) { p=p->next; j++; } if(!p) return NULL; e = p->data; return e; } //显示一个链表数据 void DisplayList(LinkList L) { cout<<"链表中的元素为："<<endl; LinkList p; p=L->next; while(p) { cout<<p->data<<" "; p=p->next; } cout<<endl; } //反转一个链表 void ReverseList(LinkList L) { if(NULL==L) return ; else if(NULL==L->next) return; else { LinkList p1=L; p1=p1->next; LinkList p2=p1->next; p1->next=NULL; LinkList p3; while(p2) { p3=p2->next; p2->next=p1; p1=p2; p2=p3; } L->next=p1; } } //合并两个链表，前提是两个链表已经是有序的 void MergeList(LinkList La,LinkList Lb) { LinkList pa=La->next; LinkList pb=Lb->next; LinkList pc=La; while(pa&&pb) { if(pa->data<=pb->data) { pc->next=pa; pc=pa; pa=pa->next; } else { pc->next=pb; pc=pb; pb=pb->next; } } pc->next=pa?pa:pb; free(Lb); } //清空一个链表 void ClearList(LinkList L) { LinkList q; while(L->next) { q=L->next; L->next =q->next; free(q); } } //销毁一个链表 void DestroyList(LinkList L) { LinkList q; while(L->next) { q=L->next; L->next =q->next; free(q); } free(L); } int main() { LinkList head; LinkList head1; head=InitList();//初始化链表 head1=InitList(); CreateList(head,10);//创建10个元素的链表 CreateList(head1,5);//创建5个元素的链表 DisplayList(head); //显示链表 DisplayList(head1);//显示链表 MergeList(head,head1); DisplayList(head); // InsertList(head,1,'i');//在第一个位置插入‘i‘ // DisplayList(head);//显示链表 // cout<<ListLength(head)<<endl; // cout<<GetElem(head,10)<<endl; // ReverseList(head); // DisplayList(head); DestroyList(head); return 0; }