單鏈表的學(xué)習(xí)
#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);
完整的實(shí)現(xiàn)代碼如下：
#include "SSeqListTest.h"
#include<malloc.h>
#include<iostream>
using namespace std;
SSeqListTest::SSeqListTest()
{
}
SSeqListTest::~SSeqListTest()
{
}
/*這里初始化的函數(shù)為void InitLinkList(LinkList * head)佳谦；
它的參數(shù)為LinkList * head疙挺，相當(dāng)于int **P祭犯，
你需要理解透徹续崖，不理解透徹的話也可以參考之前的線性表的初始化：
線性表的初始化：
void InitList(SeqList * L)
{
L->length = 0;
}
所以可以完全照搬映跟。
但是在考研的數(shù)據(jù)結(jié)構(gòu)中制作節(jié)點(diǎn)有兩種方式：
拿簡單的順序表舉例子：
（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;
}*/
//但是實(shí)際上使用最多的初始化方式是下面這種抛寝，以后樹的章節(jié)你還會(huì)見到熊杨。
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;
}
/*按照序號(hào)來查找元素操作*/
//這里需要注意的是返回的是i個(gè)位置的指針返回類型應(yīng)該寫成ListNode *、
//大家也都知道ListNode *L=LinkList L盗舰；
//所以自然也可以這樣寫：LinkList Get(LinkList head, int i)
//兩者的效果是一樣的晶府，親自動(dòng)手一下就知道了。
//以下的函數(shù)返回時(shí)指針類型的同樣的解釋钻趋。
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;
}
}
}
/*查找節(jié)點(diǎn)值為e的節(jié)點(diǎn)并返回所對(duì)應(yīng)的指針*/
ListNode *LocateElem(LinkList head, DataType e)
{
ListNode *p;
p = head->next;
while (p)
{
if (p->data!=e)
{
p = p->next;
}
else
{
break;
}
}
return p;
}
//通過元素值定位位置川陆，缺點(diǎn)在于如果有兩個(gè)位置的數(shù)據(jù)值一樣，只能定位到前一個(gè)位置蛮位。
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個(gè)節(jié)點(diǎn)*/
while (pre->next!=NULL&&j<i-1)
{
pre = pre->next;
j++;
}
if (j!=i-1)
{
cout << "插入的節(jié)點(diǎn)位置有錯(cuò)" << endl;
return -1;
}
if ((p=(ListNode*)malloc(sizeof(ListNode)))==NULL)
{
exit(-1);
}
p->data = e;
p->next = pre->next;
pre->next = p;
return 1;
}
//根據(jù)位置刪除掉單鏈表中的元素。
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 << "刪除位置出錯(cuò)" << endl;
return -1;
}
p = pre->next;
*e = p->data;
pre->next = p->next;
/*釋放P節(jié)點(diǎn)指向的點(diǎn)*/
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);
}
}
測試函數(shù)：
int main(){
cout << "測試開始"<<endl;
LinkList L;
InitLinkList(&L);
InsertList(L,1,'a');
cout << "單鏈表長度" << ListLength(L)<<endl;
LinkList getElumByNum;
getElumByNum = Get(L, 1);
cout <<"第一個(gè)位置元素是："<< getElumByNum->data << endl;
DataType deleteElumValue;
DeleteList(L,1,&deleteElumValue);
cout << deleteElumValue << endl;
cout << "單鏈表長度" << ListLength(L) << endl;
system("PAUSE");
return 0;
}
運(yùn)行結(jié)果：
這里寫圖片描述
