typedef struct Node{
ElemType data
struct Node *next
} *LNode, *LinkList
//----------线性表的单链表基本 *** 作------------
LinkList InitList(void)//构造一个空的线性表
void DestroyList(LinkList *L)//初始条件：线性表L已存在。 *** 作结果：销毁线性表L。
LinkList MakeEmpty(LinkList L)//初始条件：线性表L已存在。 *** 作结果：将线性表L重置为空表。
int IsEmpty(LinkList L)//初始条件：线性表L已存在。 *** 作结果：判断线性表是否为空表。
int ListLength(LinkList L)//初始条件：线性表L已存在。 *** 作结果：返回线性表L结点的个数。
LNode IsLast(LinkList L)//初始条件：线性表L已存在。 *** 作结果：返回线性表L的最后一个结点（尾结点）。
LNode NewLNode(ElemType X)//构造一个数据域为X的新结点
LNode FindPrefious(ElemType X, LinkList L)//初始条件：线性表L已存在。 *** 作结果：在线性表L中寻找值为X的结点，若找到则返回该结点的前驱，否则返回NULL。
void ListDelete(LNode Pre)//初始条件：线性表L中结点P已找到。 *** 作结果：删除该结点。
void ListInsert(LNode Pre, LNode S)//初始条件：线性表L中结点P已找到，新结点S已构造。 *** 作结果：在该结点之前插入新结点X。
----------线性表的单链表基本 *** 作的算法实现------------
//我给链表设置了一个头结点,虽然它的数据域毫无意义,但它作为一个指针却意义非凡!
//它的作用我们在下面的例程中可以领教
LinkList InitList(void) //构造一个空的线性表
{
LNode Head
Head = (LNode)malloc(sizeof(struct Node))//为链表的头结点分配空间
if(!Head)
{
printf("Out of space!")
return NULL
}
Head->next = NULL
return Head//返回头结点
}
void DestroyList(LinkList *L)//初始条件：线性表L已存在。 *** 作结果：销毁线性表L。
{
LNode Head, P
if(*L)//若线性表L已存在
{
Head = *L
P = Head->next
while(!P) //把链表中除头结点外的所有结点释放
{
free(Head)
Head = P
P = Head->next
}
free(Head)//释放头结点
}
}
LinkList MakeEmpty(LinkList L)//初始条件：线性表L已存在。 *** 作结果：将线性表L重置为空表。
{
LNode Head, P
Head = *L
P = Head->next
while(!P)//把链表中除头结点外的所有结点释放
{
free(Head)
Head = P
P = Head->next
}
return (Head)//返回头结点
}
int IsEmpty(LinkList L)//初始条件：线性表L已存在。 *** 作结果：判断线性表是否为空表。
{
return L->next == NULL
}
int ListLength(LinkList L)//初始条件：线性表L已存在。 *** 作结果：返回线性表L结点的个数。
{
LNode P = L->next
int num = 0
while(P) //累积线性表L结点的个数
{
num++
P = P->next
}
return num//返回线性表L结点的个数
}
//初始条件：线性表L已存在。 *** 作结果：返回线性表L的最后一个结点（尾结点）。
LNode IsLast(LinkList L)
{
LNode P = L->next
if(P)
{
while(P->next) //遍历线性表L
P = P->next
}
return P//返回线性表L的最后一个结点，若为空表则返回NULL
}
LNode NewLNode(ElemType X)//构造一个数据域为X的新结点
{
LNode S
S = (LNode)malloc(sizeof(struct Node))//为新结点分配空间
if(!S)
{
printf("Out of space!")
return NULL
}
S->data = X
S->next = NULL
return S//返回新结点
}
//线性表L已存在。 *** 作结果：在线性表L中寻找值为X的结点，若找到则返回该结点的前驱，否则返回NULL。
LNode FindPrefious(ElemType X, LinkList L)
{
LNode P = L
while(P->next &&P->next->data != X)//遍历链表寻找值为X的结点
P = P->next
if(!P->next) //如果找不到值为X的结点,返回NULL
return NULL
else //若找到则返回该结点的前驱P
return P
}
void ListDelete(LNode Pre)//初始条件：线性表L中结点P已找到。 *** 作结果：删除该结点。
{
LNode P = Pre->next
Pre->next = P->next
free(P)
}
//初始条件：线性表L中结点P已找到，新结点S已构造。。 *** 作结果：在该结点之前插入新结点X。
void ListInsert(LNode Pre, LNode S)
{
S->next = Pre->next
Pre->next = S
}
如果还没解决你的问题，可以加我百度HI账号。
#include <iostream>using namespace std
class Node
{
friend class List
private:
Node() : m_data(0), m_pNext(NULL) {}
Node(int data, Node* next = NULL)
: m_data(data), m_pNext(next) {}
private:
int m_data
Node* m_pNext
}
class List
{
public:
List() : m_pHead(NULL), m_pTail(NULL), m_nLength(0) {}
List(int nLength, int InitData = 0, int nStep = 0) : m_nLength(nLength)
{
for (int i = 0i <nLengthi++)
{
Node* pNode = new Node(InitData)
if (i == 0)
{
m_pHead = m_pTail = pNode
}
else
{
m_pTail->m_pNext = pNode
m_pTail = pNode
}
InitData += nStep
}
}
List(const List&list) : m_pHead(NULL), m_pTail(NULL), m_nLength(0)
{
Copy(list)
}
~List()
{
Free()
}
bool IsEmpty() const
{
return (m_nLength == 0)
}
int GetLength() const
{
return m_nLength
}
List&operator=(const List&list)
{
Copy(list)
return *this
}
//输出一个已生成的链表
void Print() const
{
Node* p = m_pHead
while (p != NULL)
{
cout<<p->m_data<<" "
p = p->m_pNext
}
cout<<endl
}
//插入链表项
bool Insert(int nIndex, int data)
{
if (nIndex <0 || nIndex >m_nLength - 1)
{
return false
}
Node* pNewNode = new Node(data)
if (nIndex == 0)
{
pNewNode->m_pNext = m_pHead
m_pHead = pNewNode
}
else
{
Node* p = m_pHead
for (int i = 1i <nIndexi++)
{
p = p->m_pNext
}
pNewNode->m_pNext = p->m_pNext
p->m_pNext = pNewNode
}
m_nLength++
return true
}
//追加链表项
void Append(int data)
{
Node* pNewNode = new Node(data)
if ( IsEmpty() )
{
m_pHead = m_pTail = pNewNode
}
else
{
m_pTail->m_pNext = pNewNode
m_pTail = pNewNode
}
m_nLength++
}
//连接两个链表
void Append(const List&list)
{
Node* p = list.m_pHead
while (p != NULL)
{
Append(p->m_data)
p = p->m_pNext
}
}
//返回链表的数据项数
int GetAt(int nIndex) const
{
if ( !IsValidIndex(nIndex) )
{
return -1
}
Node* p = m_pHead
for (int i = 0i <nIndexi++)
{
p = p->m_pNext
}
return p->m_data
}
//返回链表的数据项数
int operator[](int nIndex) const
{
return GetAt(nIndex)
}
//将各链表项逆向输出
void ReversePrint() const
{
Reverse_Print(m_pHead)
cout<<endl
}
private:
void Free()
{
while (m_pHead != NULL)
{
Node* pTemp = m_pHead
m_pHead = m_pHead->m_pNext
delete pTemp
}
m_pHead = m_pTail = NULL
m_nLength = 0
}
bool IsValidIndex(int nIndex) const
{
return (nIndex >= 0 &&nIndex <m_nLength)
}
void Copy(const List&list)
{
if (this == &list)
{
return
}
Free()
Node* p = list.m_pHead
while (p != NULL)
{
Append(p->m_data)
p = p->m_pNext
}
m_nLength = list.m_nLength
}
void Reverse_Print(const Node* pNode) const
{
if (pNode == NULL)
{
return
}
Reverse_Print(pNode->m_pNext)
cout<<pNode->m_data<<" "
}
private:
Node* m_pHead
Node* m_pTail
int m_nLength
}
int main()
{
List list(10, 0, 1)
List list1(10, 10, 1)
list.Print()
list.ReversePrint()
list.Append(list1)
list.Print()
list.ReversePrint()
cout<<list[10]<<endl
cout<<list.GetAt(11)<<endl
list.Insert(15, 99)
list.Print()
return 0
}
int main()
{
Link head//链表(不带头节点)
int n
printf("输入链表的长度n: ")
scanf("%d",&n)
printf("连续输入%d个数据(以空格隔开): ",n)
head=CreateLink(n)
printf("\n原本链表的节点是: ")
DispLink(head)
LinkSort(head)
printf("\n从大到小排序之后: ")
DispLink(head)
printf("\n")
return 0
}
链表的具体存储表示为：
① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）
② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）
链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。
以上内容参考：百度百科-单链表
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）