单链表的学习
#pragma once
typedef char DataType;
class SSeqListTest
{
public:
SSeqListTest();
~SSeqListTest();
};
typedef struct Node {
DataType data;
struct Node *next;
}ListNode,*LinkList;
void InitLinkList(LinkList *head);
bool IsLinkListEmpty(LinkList head);
ListNode *Get(LinkList head,int i);
ListNode *LocateElem(LinkList head,DataType e);
int LocatePosition(LinkList head,DataType e);
int InsertList(LinkList head,int i,DataType e);
int DeleteList(LinkList head,int i,DataType *e);
int ListLength(LinkList head);
void DestroyList(LinkList head);
完整的实现代码如下：
#include "SSeqListTest.h"
#include<malloc.h>
#include<iostream>
using namespace std;
SSeqListTest::SSeqListTest()
{
}
SSeqListTest::~SSeqListTest()
{
}
/*这里初始化的函数为void InitLinkList(LinkList * head)；
它的参数为LinkList * head，相当于int **P，
你需要理解透彻，不理解透彻的话也可以参考之前的线性表的初始化：
线性表的初始化：
void InitList(SeqList * L)
{
L->length = 0;
}
所以可以完全照搬。
但是在考研的数据结构中制作节点有两种方式：
拿简单的顺序表举例子：
（1）直接制作：SeqList L
（2）间接制作：SeqList *L；
L=（SeqList *）malloc（sizeof（SeqList））；
考研中第二种考查的比较多。
void InitLinkList(ListNode *head)
{
if ((head=(LinkList)malloc(sizeof(ListNode)))==NULL)
{
exit(-1);
}
(head)->next = NULL;
cout << "分配成功" << endl;
}*/
//但是实际上使用最多的初始化方式是下面这种，以后树的章节你还会见到。
void InitLinkList(LinkList *head)
{
if ((*head=(LinkList)malloc(sizeof(ListNode)))==NULL)
{
exit(-1);
}
(*head)->next = NULL;
cout << "分配成功" << endl;
}
bool IsLinkListEmpty(LinkList head)
{
if (head->next==NULL)
{
return true;
}
return false;
}
/*按照序号来查找元素操作*/
//这里需要注意的是返回的是i个位置的指针返回类型应该写成ListNode *、
//大家也都知道ListNode *L=LinkList L；
//所以自然也可以这样写：LinkList Get(LinkList head, int i)
//两者的效果是一样的，亲自动手一下就知道了。
//以下的函数返回时指针类型的同样的解释。
ListNode * Get(LinkList head, int i)
{
ListNode *p; int j=0;
if (IsLinkListEmpty(head))
{
return NULL;
}
else if(i<1){
return NULL;
}
else
{
p = head;
while (p->next!=NULL&&j<i)
{
p = p->next;
j++;
}
if (j==i)
{
return p;
}
else
{
return NULL;
}
}
}
/*查找节点值为e的节点并返回所对应的指针*/
ListNode *LocateElem(LinkList head, DataType e)
{
ListNode *p;
p = head->next;
while (p)
{
if (p->data!=e)
{
p = p->next;
}
else
{
break;
}
}
return p;
}
//通过元素值定位位置，缺点在于如果有两个位置的数据值一样，只能定位到前一个位置。
int LocatePosition(LinkList head, DataType e)
{
ListNode *p;
int i = 1;
if (IsLinkListEmpty(head))
{
return -1;
}
p = head->next;
while (p!=NULL)
{
if (p->data==e)
{
return i;
}
else
{
p = p->next;
i++;
}
}
if (p==NULL)
{
return -1;
}
else
{
return 1;
}
}
/*在i的位置插入元素，需要找到之前的i-1的指针*/
int InsertList(LinkList head, int i, DataType e)
{
ListNode *pre, *p;
pre = head;
int j = 0;
/*找到i-1个节点*/
while (pre->next!=NULL&&j<i-1)
{
pre = pre->next;
j++;
}
if (j!=i-1)
{
cout << "插入的节点位置有错" << endl;
return -1;
}
if ((p=(ListNode*)malloc(sizeof(ListNode)))==NULL)
{
exit(-1);
}
p->data = e;
p->next = pre->next;
pre->next = p;
return 1;
}
//根据位置删除掉单链表中的元素。
int DeleteList(LinkList head, int i, DataType * e)
{
ListNode *pre, *p;
int j = 0;
pre = head;
while (pre->next != NULL&&pre->next->next!=NULL&&j<i-1)
{
pre = pre->next;
j++;
}
if (j!=i-1)
{
cout << "删除位置出错" << endl;
return -1;
}
p = pre->next;
*e = p->data;
pre->next = p->next;
/*释放P节点指向的点*/
free(p);
return 1;
}
//得到单链表的长度。
int ListLength(LinkList head)
{
LinkList p;
p = head;
int count = 0;
while (p->next!=NULL)
{
p = p->next;
count++;
}
return count;
}
//销毁单聊表
void DestroyList(LinkList head)
{
ListNode *p,*q;
p = head;
while (p!=NULL)
{
q = p;
p = p->next;
free(q);
}
}
测试函数：
int main(){
cout << "测试开始"<<endl;
LinkList L;
InitLinkList(&L);
InsertList(L,1,'a');
cout << "单链表长度" << ListLength(L)<<endl;
LinkList getElumByNum;
getElumByNum = Get(L, 1);
cout <<"第一个位置元素是："<< getElumByNum->data << endl;
DataType deleteElumValue;
DeleteList(L,1,&deleteElumValue);
cout << deleteElumValue << endl;
cout << "单链表长度" << ListLength(L) << endl;
system("PAUSE");
return 0;
}
运行结果：
这里写图片描述
