本文目录一览：
C语言、双向链表
// Node.h 声明类Node
#ifndef Node_H
#define Node_H
template <class T>
class LinkList; // 为是Node类的友员类而声明
template <class T>
class Node {
public:
friend class LinkList<T>; // 将LinkList类设为友元类
private:
T data;
Node<T> *next;
};
#endif
// LinkList.h 声明类LinkList
#ifndef LinkQueue_H
#define LinkQueue_H
#include "Node.h"
template <class T>
class LinkList {
public:
LinkList(); // 建立只有头结点的空链表
LinkList(T a[], int n); // 建立有n个元素的单链表
~LinkList(); // 析构函数
int Length(); // 求单链表的长度
T Get(int i); // 取单链表中第i个结点的元素值
int Locate(T x); // 求单链表中值为x的元素序号
void Insert(int i, T x); // 在单链表中第i个位置插入元素值为x的结点
T Delete(int i); // 在单链表中删除第i个结点
void PrintList(); // 遍历单链表，按序号依次输出各元素
private:
Node<T> *first; // 单链表的头指针
};
#endif
// LinkList.cpp
#include "LinkList.h"
/*
* 前置条件：单链表不存在
* 输 入：无
* 功 能：构建一个单链表
* 输 出：无
* 后置条件：构建一个单链表
*/
template <class T>
LinkList<T>::LinkList() {
first = new Node<T>;
first->next = NULL;
}
/*
* 前置条件：单链表不存在
* 输 入：顺序表信息的数组形式a[],单链表长度n
* 功 能：将数组a[]中元素建为长度为n的单链表
* 输 出：无
* 后置条件：构建一个单链表
*/
template <class T>
LinkList<T>::LinkList(T a[], int n) {
first = new Node<T>; // 生成头结点
Node<T> *r, *s;
r = first; // 尾指针初始化
for (int i = 0; i < n; i++) {
s = new Node<T>;
s->data = a[i]; // 为每个数组元素建立一个结点
r->next = s;
r = s; // 插入到终端结点之后
}
r->next = NULL; // 单链表建立完毕，将终端结点的指针域置空
}
/*
* 前置条件：无
* 输 入：无
* 功 能：无
* 输 出：无
* 后置条件：无
*/
template <class T>
LinkList<T>::~LinkList() {
}
/*
* 前置条件：单链表存在
* 输 入：查询元素位置i
* 功 能：按位查找位置为i的元素并输出值
* 输 出：查询元素的值
* 后置条件：单链表不变
*/
template <class T>
T LinkList<T>::Get(int i) {
Node<T> *p;
int j;
p = first->next;
j = 1; // 或p=first; j=0;
while (p && j < i) {
p = p->next; // 工作指针p后移
j++;
}
if (!p)
throw "位置";
else
return p->data;
}
/*
* 前置条件：单链表存在
* 输 入：查询元素值x
* 功 能：按值查找值的元素并输出位置
* 输 出：查询元素的位置
* 后置条件：单链表不变
*/
template <class T>
int LinkList<T>::Locate(T x) {
Node<T> *p;
int j;
p = first->next;
j = 1;
if (p && p->next) {
while (p->data != x) {
p = p->next;
j++;
}
return j;
} else
throw "位置";
}
/*
* 前置条件：单链表存在
* 输 入：插入元素x,插入位置i
* 功 能：将元素x插入到单链表中位置i处
* 输 出：无
* 后置条件：单链表插入新元素
*/
template <class T>
void LinkList<T>::Insert(int i, T x) {
Node<T> *p;
int j;
p = first;
j = 0; // 工作指针p初始化
while (p && j < i - 1) {
p = p->next; // 工作指针p后移
j++;
}
if (!p)
throw "位置";
else {
Node<T> *s;
s = new Node<T>;
s->data = x; // 向内存申请一个结点s，其数据域为x
s->next = p->next; // 将结点s插入到结点p之后
p->next = s;
}
}
/*
* 前置条件：单链表存在
* 输 入：无
* 功 能：输出单链表长度
* 输 出：单链表长度
* 后置条件：单链表不变
*/
template <class T>
int LinkList<T>::Length() {
Node<T> *p = first->next;
int i = 0;
while (p) {
p = p->next;
i++;
}
return i;
}
/*
* 前置条件：单链表存在
* 输 入：要删除元素位置i
* 功 能：删除单链表中位置为i的元素
* 输 出：无
* 后置条件：单链表删除元素
*/
template <class T>
T LinkList<T>::Delete(int i) {
Node<T> *p;
int j;
p = first;
j = 0; // 工作指针p初始化
while (p && j < i - 1) { // 查找第i-1个结点
p = p->next;
j++;
}
if (!p || !p->next)
throw "位置"; // 结点p不存在或结点p的后继结点不存在
else {
Node<T> *q;
int x;
q = p->next;
x = q->data; // 暂存被删结点
p->next = q->next; // 摘链
delete q;
return x;
}
}
/*
* 前置条件：单链表存在
* 输 入：无
* 功 能：单链表遍历
* 输 出：输出所有元素
* 后置条件：单链表不变
*/
template <class T>
void LinkList<T>::PrintList() {
Node<T> *p;
p = first->next;
while (p) {
cout << p->data << endl;
p = p->next;
}
}
#include <iostream.h>
#include "LinkList.cpp"
#include "Node.h"
void main() {
LinkList<int> a;
cout << "执行插入操作:" << endl;
try {
a.Insert(1, 4);
a.Insert(2, 5);
a.Insert(3, 6);
} catch (char *wrong) {
cout << wrong; // 如失败提示失败信息
}
cout << "已经插入“4，5，6”" << endl;
cout << "单链表a的长度为:" << endl;
cout << a.Length() << endl; // 返回单链表长度
cout << endl;
cout << "单链表a的元素为:" << endl;
a.PrintList(); // 显示链表中所有元素
cout << endl;
cout << "按位查找第二个元素:" << endl;
cout << "第二个元素为:";
cout << a.Get(2) << endl; // 查找链表中第二个元素
cout << endl;
cout << "按值查找5" << endl;
cout << "值为5的元素位置为:";
cout << a.Locate(5) << endl; // 查找元素5，并返回在单链表中位置
cout << endl;
cout << "执行删除4的操作" << endl;
a.Delete(1); // 删除元素4
cout << "已删除成功，单链表a的长度为";
cout << a.Length() << endl;
cout << endl;
cout << "链表a中的元素为:" << endl;
a.PrintList();
int r[] = {1, 2, 3, 4, 5};
LinkList<int> b(r, 5); // 根据数组创建顺序表
cout << "执行插入操作前单链表b为:" << endl;
b.PrintList(); // 输出单链表所有元素
cout << "插入前单链表b的长度为:";
cout << b.Length() << endl;
try {
b.Insert(3, 8);
} catch (char *wrong) {
cout << wrong; // 如失败提示失败信息
}
cout << "执行插入操作后单链表b为:" << endl;
b.PrintList(); // 输出单链表b所有元素
cout << "插入后单链表b的长度为:";
cout << b.Length() << endl;
cout << endl;
try {
if (a.Length()) {
cout << "执行删除第一个元素操作:" << endl;
cout << endl;
b.Delete(1); // 删除b中第一个元素
cout << "已删除成功，单链表b的长度为:";
cout << b.Length() << endl;
} else {
cout << "顺序表b长度为0" << endl;
}
} catch (char *wrong) {
cout << wrong; // 如失败提示失败信息
}
cout << "执行插入操作后单链表b为:" << endl;
b.PrintList(); // 输出单链表所有元素
}
C语言双向链表
#include "stdio.h"
#include "stdlib.h"
typedef int ElemType; // 元素类型
typedef struct DuLNode {
// 双向链表
ElemType data;
struct DuLNode *prior, *next;
} DuLNode, *DuLinkList;
int Create(DuLinkList L) {
// 建立双向链表
DuLinkList p, q;
ElemType n, i;
L = (DuLinkList)malloc(sizeof(DuLNode));
L->next = NULL;
q = L;
printf("输入数据个数:");
scanf("%d", &n);
printf("输入数据元素:");
for (i = 0; i < n; i++) {
p = (DuLinkList)malloc(sizeof(DuLNode));
scanf("%d", &p->data); // 插入数据
p->prior = q;
q->next = p;
p->next = 0;
q = q->next;
}
return 1;
}
int Visit(DuLinkList L) {
// 遍历双向链表
DuLinkList p;
p = L->next;
printf("双向链表为:");
while (p) {
printf("%4d", p->data);
p = p->next;
}
printf("\n");
return 1;
}
int Clear(DuLinkList L) {
DuLinkList p;
p = L->next;
while (p) {
L->next = p->next;
free(p);
p = L->next;
}
return 1;
}
main() {
int i, e, s, num;
char c = 'y';
DuLinkList L;
Create(L);
Visit(L);
while (c == 'y') {
printf("\n\n\n1.双向链表插入元素\n2.双向链表中删除元素\n");
printf("3.判断双向链表元素是否对称\n");
printf("4.双向链表中奇数排在偶数前面\n");
printf("5.建立递增链表并有序插入元素\n\n");
printf("选择需要的操作\n\n");
scanf("%d", &num);
switch (num) {
case 1:
printf("输入插入元素位置以及元素:\n");
scanf("%d%d", &i, &e);
ListInsert(L, i, e);
Visit(L);
break;
case 2:
printf("输入删除元素位置:");
scanf("%d", &i);
Delete(L, i, s);
printf("删除的元素为:%d\n", s);
Visit(L);
break;
case 3:
if (Same(L))
printf("链表对称\n");
else
printf("链表不对称\n");
break;
case 5:
printf("清空原链表，建立递增链表:\n");
XCreate(L);
Visit(L);
break;
case 4:
printf("奇数放在偶数前面:\n");
Jiou(L);
Visit(L);
break;
}
printf("继续操作(y/n):\n");
scanf("%s", &c);
}
}
C语言定义双向链表结构体
struct node {
DataType data;
struct node *prior;
struct node *next;
};
其中 prior 指针用来存储前一节点的地址，next 用来存储后一节点的地址，就比单项链表多了一个指针而已，可以添加其它自定义的数据成员。
使用C语言实现双向链表的建立、删除和插入
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
struct list {
int data;
struct list *next;
struct list *pre;
};
typedef struct list node;
typedef node *link;
link front = NULL, rear, ptr, head = NULL;
link push(int item) {
link newnode = (link)malloc(sizeof(node));
newnode->data = item;
if (head == NULL) {
head = newnode;
head->next = NULL;
head->pre = NULL;
rear = head;
} else {
rear->next = newnode;
newnode->pre = rear;
newnode->next = NULL;
rear = newnode;
}
return head;
}
void makenull() {
front = NULL;
rear = NULL;
}
empty() {
if (front == NULL)
return 1;
else
return 0;
}
int tops() {
if (empty())
return NULL;
else
return rear->data;
}
void pop() {
if (empty())
printf("stack is empty!\n");
else
rear = rear->pre;
}
void display(link l) {
link p;
p = l;
while (p != NULL) {
printf("%d-", p->data);
p = p->next;
}
}
void main() {
int n, i;
printf("input your first data!\n");
scanf("%d", &n);
front = push(n);
/* another data */
for (i = 0; i < 3; i++) {
printf("input:\n");
scanf("%d", &n);
push(n);
}
ptr = front;
display(ptr);
printf("\n Please enter any key to pop");
pop();
ptr = front;
display(ptr);
}
求问c语言单向链表和双向链表与循环链表的区别
打个比方。把链表节点看作是一个人，把链表指针看作是人的手（左手是前向指针，右手是后向指针）。 非循环的单向链表 是这样的：若干个人排成一排，每个人都抬起右手指向他右边的人，最右边的人的右手指向了空气（NULL）。如果要想找到这一排中任意一个人，必须从排头（链表头）开始沿手指的方向挨个查找。 循环单向链表 是这样的：若干个人围成一圈，每个人都抬起右手指向他右边的人，这样每个人的右手都能指到一个人（如果只有一个人，那么他的右手指向自己）。从任意一个人开始，沿着手指的方向，可以不停地循环找到每一个人。 非循环的双向链表 是这样的：若干个人排成一排，每个人都抬起左手指向他左边的人，并且每个人都抬起右手指向他右边的人，那么最左边的人的左手指向了空气（NULL），最右边的人的右手指向了空气（NULL）。如果要想找到这一排中某个目标人，从任意一个人开始，可以沿左手方向尝试查找，如果找不到，可以继续沿右手方向查找，直到找到目标人。 循环双向链表 是这样的：若干个人围成一圈，每个人都抬起左手指向他左边的人，并且每个人都抬起右手指向他右边的人，这样每个人的左右手都可以指到一个人（如果只有一个人，那么他的左右手都指向自己）。无论选择左手方向还是右手方向，都可以不停地循环找到每一个人。
