用C语言编写程序建立链表结构体类型实现链表初始化遍历和插入算法

Question

如题所述

Answer 1

#include <stdio.h>
#include <stdlib.h>

#define telemtype char
#define ok 1
#define error 0
#define overflow -1

typedef int status;

typedef struct bitnode
{
telemtype data;
struct bitnode *lchild,*rchild;
}bitnode,*bitree;

void preordertraverse(bitree T)
{
if(T)
{
printf("%c ",T->data);
preordertraverse(T->lchild);
preordertraverse(T->rchild);
}
}

status createbitree(bitree &T)
{
int ch;
ch=getchar();
if(ch==' ')
T=NULL;
else
{
if(!(T=(bitnode*)malloc(sizeof(bitnode))))
exit(overflow);
T->data=ch;
createbitree(T->lchild);
createbitree(T->rchild);
}
return ok;
}

void prinbtree(bitree T)
{
if(T!= NULL)
{

printf("%c", T->data);
if(T->lchild!=NULL||T->rchild!=NULL)
{
printf("(");
prinbtree(T->lchild);
if(T->rchild!=NULL)
{
printf(",");
}
prinbtree(T->rchild);
printf(")");
}
}
}

int main()
{
bitree T=NULL;

printf("先序输入二叉树：\n");
createbitree(T);

printf("先序遍历二叉树为：\n");
preordertraverse(T);
printf("\n");

prinbtree(T);
printf("\n");

return 0;
}

我写的，希望对你有用！

Answer 2

我的C++ 链表源码 你可以参考下 你把 class 改成struct 就差不多了
个人源码（自编模板整合）
2010-09-28 16:47 (分类:默认分类)
#include<iostream>
using namespace std;
template <typename T>
struct Node
{
T data;
Node<T> *next;
};

template <typename T>
class Sqlist
{
private:
Node<T> *head;
public:
Sqlist()
{
head=NULL;
}
~Sqlist()
{
Node<T>*p;
while(head)
{
p=head->next;
delete head;
head=p;
}
}
bool push(T x);
bool empty();
int length();
bool output();
bool replace(T x,T x2);
Node<T> *theone_find(int n,int i);
bool thetwo_insert(int i,T x);
bool thethree_Delete(int i,int n);
bool thefour_insert(T x);
void thefive(int k);
bool the_six(Sqlist<T> L2);
//bool clear();
};

template <typename T>
bool Sqlist<T>::push(T x)
{
if(head==NULL)
{
Node<T>*p=new Node<T>;
p->data=x;
p->next=NULL;
head=p;
}
else {
Node<T> *p=head;
while(p->next!=NULL)p=p->next;
Node<T>*q=new Node<T>;
q->data=x;
q->next=NULL;
p->next=q;
}
return true;
}

template <typename T>
bool Sqlist<T>::thethree_Delete(int i,int n)
{
Node<T> *p=head;
if(i<=0||i>n)return false;
if(i==1){head=p->next;delete p;return true;}
for(int j=2;j<i;j++)p=p->next;
Node<T>*q=p->next;
p->next=q->next;
delete q;
return true;
}

template <typename T>
bool Sqlist<T>::empty(){
return head==NULL;
}
template <typename T>
int Sqlist<T>::length(){
Node<T> *p=head;
int n=0;
while(p!=NULL){n++;p=p->next;}
return n;
}
template <typename T>
bool Sqlist<T>::output(){
Node<T> *p=head;
if(p==NULL)return false;
while(p!=NULL){cout<<p->data<<" ";p=p->next;}
cout<<endl;
return true;
}

template <typename T>
bool Sqlist<T>::replace(T x,T x2){
if(find(x)==NULL)return false;
Node<T> *p=find(x);
p->data=x2;
}

template <typename T>
Node<T> *Sqlist<T>::theone_find(int n,int i){
Node<T> *p=head;
if(i>n||i<=0){p=NULL;return p;}
for(int j =1;j<i;j++)p=p->next;
return p;
}

template <typename T>
bool Sqlist<T>::thetwo_insert(int i,T x){
if(i>length()||i<0)return false;
if(i==length()){push(x);return true;}
Node<T>*p=new Node<T>;
p->data=x;
if(i==0){p->next=head;head=p;return true;}
Node<T>*q=head;
while(--i)q=q->next;
p->next=q->next;
q->next=p;
return true;
}

template <typename T>
bool Sqlist<T>::thefour_insert(T x){
Node<T>*p=head;
if(x<p->data){
Node<T>*q=new Node<T>;
q->data=x;
q->next=p;
head=q;
return true;
}
while(p->next!=NULL){
if(x<p->next->data)break;
p=p->next;}
if(p->next==NULL){
Node<T>*q=new Node<T>;
q->data=x;q->next=NULL;
p->next=q;
}
else {
Node<T>*q=new Node<T>;
q->data=x;
q->next=p->next;
p->next=q;
}
return true;
}

template <typename T>
void Sqlist<T>::thefive(int k)
{
Sqlist<T> a,b;
Node<T>*p=head;
for(int i=1;i<=k;i++)
{
if(i%2!=0){
a.push(p->data);
}
else b.push(p->data);
p=p->next;
}
a.output();
b.output();
}

template <typename T>
bool Sqlist<T>::the_six(Sqlist<T> B)
{
Node<T>*p=head;
Node<T>*q=B.head;
Sqlist<T>L3;
while(p!=NULL)
{

while(q!=NULL)
{
if(p->data==q->data){L3.push(p->data);break;}
q=q->next;
}
p=p->next;
}
L3.output();
//cout<<"-----------"<<endl;
return true;
}

int main(){
for(;;){
cout<<"1.求链表中第i个结点的指针"<<endl;
cout<<"2.在第i个结点前插入值为x的结点"<<endl;
cout<<"3.删除链表中第i个元素结点"<<endl;
cout<<"4.在一个递增有序的链表L中插入一个值为x的元素"<<endl;
cout<<"5.奇数项和偶数项结点分解开"<<endl;
cout<<"6.L1和L2中的公共元素"<<endl;
int a;
cin>>a;
switch(a)
{
case 1:
{
Sqlist<int> A;
int n,a;
cout<<"请输入n"<<endl;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a;A.push(a);
}
int i;
for(;;){
cout<<"请输入i"<<endl;
cin>>i;
Node<int> *p;
p=A.theone_find(n,i);
if(p==NULL)cout<<"NULL"<<endl;
else cout<<"!NULL"<<endl;
int l;
cout<<"继续查找吗？否（1）是（2）"<<endl;
cin>>l;
if(l==1)break;
}
break;
}
case 2:{
Sqlist<int> A;
int n,a;
cout<<"请输入n"<<endl;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a;A.push(a);
}
for(;;)
{
int i;int x;
cout<<"请输入位置i 数据x"<<endl;
cin>>i>>x;
if(A.thetwo_insert(i-1,x)){cout<<"成功！"<<endl;
A.output();}
else cout<<"失败！！"<<endl;
char l;
cout<<"继续插入吗？否（n）是（Y）"<<endl;
cin>>l;
if(l=='n')break;
}
break;
}
case 3:{
Sqlist<int> A;
int n,a;
cout<<"请输入n"<<endl;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a;A.push(a);
}
for(;;){
cout<<"请输入i"<<endl;
int i ;cin>>i;
if(A.thethree_Delete(i,n)){cout<<"YES"<<endl;
A.output();}
else cout<<"NO!!"<<endl;
char l;
cout<<"继续删除吗？否（n）是（Y）"<<endl;
cin>>l;
if(l=='n')break;
}
break;
}
case 4:{
Sqlist<int> A;
int n,a;
cout<<"请输入n"<<endl;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a;A.push(a);
}
for(;;)
{
int x;
cout<<"请输入X"<<endl;
cin>>x;
A.thefour_insert(x);
A.output();
char l;
cout<<"继续插入吗？否（n）是（Y）"<<endl;
cin>>l;
if(l=='n')break;
}
break;
}
case 5:{
Sqlist<int> A;
int n,a;
cout<<"请输入n"<<endl;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a;A.push(a);
}
A.thefive(n);
cout<<endl;
A.output();
break;
}
case 6:{
Sqlist<int> A,B;
int n,a;
cout<<"请输入L1的n"<<endl;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a;A.push(a);
}
cout<<"请输入L2的n"<<endl;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a;B.push(a);
}
if(A.the_six(B))break;

}

default:{cout<<"选择错误！！"<<endl;break;}
}

char l;
cout<<endl;
cout<<endl;cout<<endl;
cout<<"------还需要测试其他功能吗？否（n）是（y）------"<<endl;
cin>>l;
if(l=='n')break;
system("cls");
}
return 0;
}