数据结构之链表实现
主要包括了链表操作中的创建，插入元素、删除元素，元素定位以及链表合并等操作。
***************************************************************************
* 声明：本文所有内容均为原创，转载请声明出处 *
* blog: http://blog.csdn.net/weixingstudio *
* watkins.song *
***************************************************************************
// LinkList.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include "iostream"#include "stdlib.h"#include "stdio.h"using namespace std;typedef int DataType;// 定义链表中的结点typedef struct LNode{DataType data;struct LNode *next;}LNode, *LinkList;void CreateList(LinkList &L,int n);void PrintLinkList(LinkList &L);int GetElem(LinkList L, int i, DataType &e);int ListInsert(LinkList &L,int i, DataType e);int ListDelete(LinkList &L, int i, DataType &e);void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc);int _tmain(int argc, _TCHAR* argv[]){// 创建一个指定长度的链表int LinkListLength=6;LinkList L;CreateList(L,LinkListLength);// 输出链表PrintLinkList(L);// 查找第3个元素int tobefound=0;GetElem(L,3,tobefound);printf("\ntobefound=%d\n",tobefound);// 在指定位置插入一个新的结点ListInsert(L,3,10);// 输出链表printf("new node is inserted:\n");PrintLinkList(L);// 删除一个指定位置的链表结点int e;ListDelete(L,4,e);// 输出链表printf("\none node is deleted:\n");PrintLinkList(L);// 创建新的链表printf("\ninput 3 new nodes of new list\n");LinkList L2;CreateList(L2,3);PrintLinkList(L2);// 合并两个链表LinkList L3;MergeList(L,L2,L3);printf("\nMerged lists:\n");PrintLinkList(L3);//getchar();getchar();return 0;}// 创建长度为n的链表void CreateList(LinkList &L,int n){//L=(LinkList)malloc(sizeof(LNode));L->next=NULL;printf("please input n link nodes \n");for(int i=n;i>0;--i){LNode *p=(LinkList)malloc(sizeof(LNode));scanf("%d",&p->data);// 在链表头部插入新的结点p->next=L->next;L->next=p;}}// 输出链表中结点void PrintLinkList(LinkList &L){printf("all list nodes is : \n");LinkList p=L->next;// 指向第一个结点while(p!=NULL){printf("%5d",p->data);p=p->next;}}// 查找链表元素,查找第i个元素int GetElem(LinkList L, int i, DataType &e){// LinkList p=L->next;// 指向第一个元素int j=1;while(p&&j<i){//p=p->next;j++;}if(!p||j>i) return -1; // 没有查找到e=p->data;return 1; // 表示查找到}// 在第i个结点之前插入元素eint ListInsert(LinkList &L,int i, DataType e){LinkList p=L;int j=0;while(p&&j<i-1){p=p->next;++j;} // 直到p指向i-1if(!p||j>i-1) return -1;LinkList s=(LinkList)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;}// 删除指定位置的结点,删除第i个结点int ListDelete(LinkList &L, int i, DataType &e){// LinkList p=L; // 指向头结点int j=0;while(p->next&&j<i-1){p=p->next;j++;}if(!(p->next)||j>i-1) return -1;LinkList q=p->next; // 指向被删除的结点p->next=q->next;e=q->data;free(q);}// 合并两个链表void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc){LinkList pa=La->next; //指向第一个元素LinkList pb=Lb->next; //指向第一个元素LinkList pc=La; // 以La链表的头结点为合并后的链表的头结点Lc=pc;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);}