*链表应用要求:1建立 2删除 3输出 4反序 5主函数
*/
#include<iostream>
#include<iomanip>
using namespace std
typedef struct Lnode{
int data
struct Lnode *next
}Lnode,*LinkList
//初始化链表
bool initList(LinkList &L)
{
L=new Lnode
if(L==NULL){
cerr<<"内存分配错误!"<<endl
return false
}
L->next=NULL
return true
}
//创建链表
bool createList(LinkList &L)
{
int n,data
LinkList p=L,r
cout<<"输入链表元素的个数:"
cin>>n
cout<<"输入链表中的元素:"
for(int i=0i<n++i){
cin>>data
r=new Lnode
if(r==NULL){
cerr<<"内存分配错误!"<<endl
return false
}
r->data=data
r->next=p->next
p->next=r
p=r
}
p->next=NULL
return true
}
//删除链表中的元素
bool deleteList(LinkList L)
{
int pos
LinkList p=L
if(p->next==NULL){
cout<<"链表是空的!"<<endl
return false
}
cout<<"输入你要删除的位置:"
cin>>pos
for(int i=0i<pos-1++i){
p=p->next
}
LinkList q=p->next
cout<<"你删除的第"<<pos<<"个位置的元素是:"<<q->data<<endl
p->next=q->next
delete q
return true
}
//逆序输出链表中的元素
bool invertList(LinkList &L)
{
LinkList p=L->next
if(p==NULL) return false
else invertList(p)//采用递归的方式逆序输出链表
cout<<p->data<<setw(5)
return true
}
//输出链表中的元素
bool dispList(LinkList L)
{
LinkList p=L->next
if(p==NULL){
cout<<"链表是空的!"<<endl
return false
}
cout<<"链表中的元素为:"
while(p){
cout<<p->data<<setw(5)
p=p->next
}
cout<<endl
return true
}
void main()
{
LinkList L
initList(L)
createList(L)
dispList(L)
deleteList(L)
dispList(L)
cout<<"逆序输出的元素为:"
invertList(L)
cout<<endl
}
题目中的将链表逆序,如果用单链表实现有点麻烦,我再想想有没有好的办法。
上面的程序中我只是将链表的元素逆序输出,至于将链表逆序,我想好了会回复你的。
如下:#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int data
node* pNext
}Node
//链表的操作,以有头节点为例,无头节点类似
Node* head = NULL
//创建链表,头结点data=0,pNext=NULL
bool createNodeList()
{
head = (Node*) malloc(sizeof(Node))
if(NULL == head)
{
return false
}
else
{
head->data = 0
head->pNext = NULL
return true
}
}
//增加节点
bool addNode(Node* node)
{
if(NULL == head)
{
return false
}
Node* p = head->pNext
Node* q = head
while(NULL != p)
{
q = p
p = p->pNext
}
q->pNext = node
node->pNext = NULL
return true
}
//删除节点
bool deleteNode(int index)
{
if(NULL == head)
{
return false
}
Node* p = head->pNext
int length = 0
while(NULL != p)
{
length ++
p = p->pNext
}
if(length <index)
{
return false
}
else
{
Node* q = head
p = head
for(int i=0i<indexi++)
{
q = p
p = p->pNext
}
Node* t = p->pNext
q->pNext = t
free(p)
return true
}
}
//逆序
void reverseNodeList()
{
if(NULL == head)
{
return
}
//如果链表长度为1
if(head->pNext == NULL)
{
return
}
Node* p = head->pNext
Node* q = p->pNext
Node* t = NULL
while(NULL != q)
{
t = q->pNext
q->pNext = p
p = q
q = t
}
head->pNext->pNext = NULL
head->pNext = p
}
//排序(降序)
void sort()
{
//冒泡排序
Node* pHead = head
if(head == NULL)
{
return
}
if(pHead->pNext == NULL)
{
return
}
Node* pi = pHead->pNext
Node* pj = pi->pNext
for(pi != NULLpi=pi->pNext)
{
for(pj = pi->pNextpj != NULLpj=pj->pNext)
{
if(pj->data>pi->data)
{
int tmp = pj->data
pj->data = pi->data
pi->data = tmp
}
}
}
}
//销毁
void destroyNodeList()
{
if(NULL == head)
{
return
}
if(NULL == head->pNext)
{
free(head)
head = NULL
return
}
Node* p = head->pNext
while(NULL != p)
{
Node* tmp = p
p = p->pNext
free(tmp)
}
free(head)
head = NULL
}
void main()
{
createNodeList()
Node* node1 = (Node*)malloc(sizeof(Node))
node1->data = 1
node1->pNext = NULL
Node* node2 = (Node*)malloc(sizeof(Node))
node2->data = 2
node2->pNext = NULL
修改了两个地方,详见注释:
NODE *revrese(NODE *head){ // 由于你的链表是不带头结点的,所以要采用头指针的算法
NODE *p1,*p2,*p3
p1=head
p2 = p3 = NULL
while(p1) {
p2=p1->next // 防止断链,让q2临时指向p1的后继
p1->next=p3 // 反复令前驱变后继,后继变前驱
p3=p1 // 使当前链表作为下次要改变为后继的链表。
p1=p2 // 继续处理下一个结点
}
return p3
}
void main(){
NODE *head
head=creat()
print(head)
printf("\n")
print(revrese(head)) // 逆转函数返回一个头指针指向逆转的链表。
}