数据结构之链表实现
主要包括了链表操作中的创建,插入元素、删除元素,元素定位以及链表合并等操作。
[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++ ,