当前位置:编程学习 > C/C++ >>

数据结构之链表实现

主要包括了链表操作中的创建,插入元素、删除元素,元素定位以及链表合并等操作。
 
 
 
 
 
 
[cpp] 
// 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个结点之前插入元素e   
int ListInsert(LinkList &L,int i, DataType e)  
{  
    LinkList p=L;  
    int j=0;  
    while(p&&j<i-1)  
    {  
        p=p->next;  
        ++j;  
    } // 直到p指向i-1   
    if(!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)  
    {  
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,