欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

单链表的基本操作

程序员文章站 2024-03-05 23:22:49
...
#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;

typedef char ElemType;
#define ERROR -1
#define OK 1

typedef struct Node{
	ElemType data;
	struct Node *next;
}Node, *LinkList;

LinkList CreateList()
{
	LinkList L;
	char c;
	Node *r, *s;
	int flag = 1;
	L = (LinkList)malloc(sizeof(Node));
	L->next = NULL;
	r = L;
	while(flag)
	{
		cin >> c;
		if(c != '#')
		{
			s = (Node *)malloc(sizeof(Node));
			s->data = c;
			r->next = s;
			r = s;
		}
		else
		{
			flag = 0;
			r->next = NULL;
		}
	}
	return L;
}

void PrintList(Node *L)
{
	Node *p;
	p = L->next;
	while(p != NULL)
	{
		cout << p->data << " " ;
		p = p->next;
	}
	cout << endl;
}

Node * GetList(LinkList L, int i)
{
	int j;
	Node *p;
	if( i <= 0)
	{
		return NULL;
	}
	p = L;
	j = 0;
	while(p->next != NULL && j < i)
	{
		p = p->next;
		j++;
	}
	if(i == j)
	{
		return p;
	}
	else
	{
		return NULL;
	}
}

Node * LocateList(LinkList L, ElemType e)
{
	Node *p;
	p = L->next;
	while(p != NULL)
	{
		if(p->data != e)
		{
			p = p->next;
		}
		else
		{
			break;
		}
	}
	return p;
}

int InsertList(LinkList L, int i, ElemType e)
{
	Node *pre, *s;
	int k;
	if(i <= 0)
	{
		return ERROR;
	}
	pre = L;
	k = 0;
	while(pre != NULL && k < i - 1)
	{
		pre = pre->next;
		k++;
	}
	if(!pre)
	{
		printf("输入的位置不合理!\n");
		return ERROR;
	}
	s = (Node *)malloc(sizeof(Node));
	s->data = e;
	s->next = pre->next;
	pre->next = s;
	return OK;
}

int DeleteList(LinkList L, int i)
{
	Node *pre , *r;
	int k;
	pre = L;
	k = 0;
	while(pre->next != NULL && k < i - 1)
	{
		pre = pre->next;
		k++;
	}
	if(!(pre->next))
	{
		printf("删除的位置不合理!\n");
		return ERROR;
	}
	r = pre->next;
	pre->next = r->next;
	free(r);
	return OK;
}

int listLength(LinkList L)
{
	int j;
	Node *p;
	p = L->next;
	j = 0;
	while(p != NULL)
	{
		p = p->next;
		j++;
	}
	return j;
}

void FreeList(LinkList L)
{
	if(L->next != NULL)
	{
		FreeList(L->next);
	}
	free(L);
}

int scan()
{
	int n;
	cout << "-----------------++++++++++++++++++-------------------" << endl;
	cout << "                请选择所要进行的操作                  " << endl;
	cout << "1、链表的生成,输入#终止                              " << endl;
	cout << "2、输出链表的长度                                     " << endl;
	cout << "3、遍历链表的元素                                     " << endl;
	cout << "4、按序号查找      5、按值查找                        " << endl;
	cout << "6、链表元素的插入  7、链表元素的删除                  " << endl;
	cout << "-----------------++++++++++++++++++-------------------" << endl;
	cin >> n;
	return n;
}

int main()
{
	LinkList L;
	int quit = 0;
	int i;
	ElemType e;
	Node *p;
	while(!quit)
	{
		switch(scan())
		{
			case 1 : L = CreateList();break;
			case 2 : cout << "链表的长度为:" << listLength(L) << endl << endl;break;
			case 3 : PrintList(L);break;
			case 4 : cout << "请输入要查找的序号" << endl; cin >> i; p = GetList(L,i);cout << "查找的元素为:" << p->data << endl;break;
			case 5 : cout << "请输入要查找的元素" << endl; cin >> e; p = LocateList(L,e);break;
			case 6 : cout << "请输入要插入的元素和位置" << endl; cin >> e >> i;InsertList(L,i,e);break;
			case 7 : cout << "请输入要删除的元素的位置" << endl; cin >> i; DeleteList(L,i);break;
			default: quit = 1;
		}
	}
	return 0;
}

转载于:https://www.cnblogs.com/lgh1992314/archive/2013/03/07/5835175.html