【数据结构】ds笔记1-数据结构基础

说在前面

本篇笔记总结了DSPv2b_1(数据结构基础) for student内的相关内容，将ppt分为两个部分————知识点和例题，其中例题并不包括ppt中的全部内容（删减了一些本人认为难度较小的例题，才...才不是因为懒得写呢）。如果代码中出现了全角字符，请原谅喵，因为有的代码我没有cv到clion里面去检查（戳手）。以及本人学艺不精，只是一边看着ppt一边敲敲改改，如有疏漏，欢迎提出喵~o( =∩ω∩= )m

知识点

2.1 递归

使用递归的基本法则：

  • 基本实例(base case)：问题的解包含一个或多个基本实例，如0! = 1，它们不用递归就能直接求解
  • 递进(making progress)：问题的解可以简化为包含比当前问题更简单一步的问题的解，并且最终问题可归结到基本实例，如n! = n*(n-1)!；或者一个问题可分解为若干子问题来解决（分治），如树遍历或快速排序等，但最终也要归结到基本实例。即递归调用必须朝着产生基本实例的方向推进

2.2 数组

2.2.1 数组作为函数参数

  • 数组作为参数传递给函数，实际上传递的是数组的首地址，即他们是一个数组，在函数中对数组的操作会在函数外有所体现。

  • 非字符数组作为参数时，函数的定义形式（字符数组还需要在形参中置顶数组元素个数）：

    1
    2
    3
    void fun(int array[], int size){
        ...
    }

  • 数组作为参数时，函数的调用形式

    1
    2
    3
    4
    5
    6
    int main(){
        int a[10];
        ...
        fun(a, 10);
        ...
    }

2.2.2 二维（多维）数组使用

  • 如果把一个二维数组作为参数，则在函数定义中，形参数组的说明中必须指明列的数目，而行的数目可空着不写。以此类推，对于三维及以上数组，其作为参数传递时，形参说明中只能省略最内层的维数。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    int main( ){
    	float a[4][3], b[3][4], c[4][4];
        ...
    	fun(a, b, c);
        ...
    }
    void fun(float x[ ][3], float y[ ][4], float z[ ][4]){
    	...
    }

2.3 指针

2.3.1 指针

  1. 指针变量的定义：<类型> *<变量>，例：

    1
    2
    3
    4
    5
    6
    char *pc;			//指向字符型的指针
    char *acp[10];		//由指向字符的指针构成的数组，即指针数组
    char (*pac)[10];	//指向字符数组的指针，即数组指针
    int f( );			//返回值为整型的函数
    int *fpi( );		//返回值为指向整型的指针的函数，即指针函数
    int (*pfi)();		//指向一个返回值为整型的函数的指针，函数指针

  2. 指针运算符：&取地址运算符，*取内容运算符。

  3. 使用任何指针变量之前必须先给它赋一个所指合法具体对象的地址值。

    1
    2
    3
    4
    5
    6
    7
    8
    //错误示范
    int x = 1;
    int *px;
    *px = x;
    //错误示范
    char *string;
    scanf("%s", string);
    strcpy(string, "Hello");

  4. 如何使一个指针指向一个具体对象：

    1. 通过&运算符使指针指向某个对象。如：

      1
      2
      int n=10, *px;
      px = &n;

    2. 将另一个同类型的（已指向具体对象的）指针赋给它以获得值，两指针指向同一对象。如：

      1
      2
      3
      4
      5
      int n=10, *px,*py;
      char str[10],*pstr;
      px = &n; 
      py = px;
      pstr = str;

    3. 使用malloc或alloc等函数给指针分配一个具体空间（动态存储分配）。如:

      1
      p = (char *)malloc(strlen(s)+1);

      动态内存管理（malloc与free）

      • 在C语言中可以使用标准库函数malloc动态为指针变量申请一块内存空间（以字节为单位）（用于初始化指针变量），并返回该空间首地址。

      • 函数原型为：void * malloc ( size_t size );

      • 使用malloc初始化指针变量的常见用法：

        char *s; 
int *intptr;
s = (char *)malloc(32); 
// s指向大小为32个字节（字符）的空间
s = (char *)malloc(strlen(p)+1);
// s指向能正好存放字符串p的空间
intptr = (int *)malloc(sizeof(int)*10);
// ptr指向能存放10个整型元素的空间

      • 使用malloc申请到的动态空间在不用时应使用函数free释放。如，free(s);

      • 使用malloc和free函数要用：

        #include stdlib.h

  5. 指针运算

    1. 指针和整型量可以进行+-。其结果同指针所指对象类型相关。如果p是指向数组某一元素的指针，则p+1及p++为数组下一元素的指针。

    2. 指向同一数组成员的指针可以相减。其结果为两指针间相差元素的个数。如，p指向数组第一个元素，q指向数组最后一个元素,则q – p+1表示数组长度。

    3. 指向同一类型的指针可以赋值。

    4. 指向同一类型的指针可以进行==, >, <等关系运算。用于比较地址

    5. 指针不能相加。如：

      1
      2
      3
      int a[100], *start = &a, *end = &a[99];
      mid = (low+high)/2;			//错误！！！
      mid = low+(high-low)/2;		//正确

    6. tips：

      1. p++和p+1的区别；

        p++结果为p指向下一元素；p+1结果为下一元素的指针，但p本身不变。

      2. y = (*px)++和y = *px++的区别；

        (*px)++为先取px所指对象内容进行运算，然后对其加1；px++为先取px所指对象内容进行运算，然后指针px加1，其等价于*(px++)。

  6. 指针作为函数参数

    1. c语言中函数的参数传递方式为“传值”，使得函数调用不会改变实参变量的值。但可以将指针作为函数参数来改变实参内容，如：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      //通过函数swap交换实参变量a和b
      void swap ( int *px, int *py){
          int temp;
          temp = *px;  /*间接取*/
          *px = *py;	/*间接取，间接存*/
          *py = temp;	/*间接存*/
      }
      int main( ){
          int a =2, b = 3;
          swap ( &a, &b);
      }

    2. 因此，在一定要改变实参变量内容时，应把函数的形参显式地说明为指向实参变量（类型）的指针，相应地调用时应该用变量的地址值作为参数。

2.3.2 函数指针

  • 简介

    • 即指向函数的指针

    • 函数指针说明形式为类型 (*标识符)( );，如int(*fp)();

    • 辨析：int(*fp)();与int *fp();不同，前者是一个指针，指向一个返回值类型是int的函数；后者是一个函数，其返回值的类型是int*

    • 函数指针的复制：函数指针 = 函数名，（在c语言中，函数名是作为该函数的指针来处理，也就是说函数名就是指向函数的指针）

    • 在c语言中，通过函数指针调用一个函数时，(*fnptr)(2000)与fnptr(2000)用法等价

    • 例：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      int leapyear( int year);
      main( ){
          int (*fnptr)( ),result;
          fnptr = leapyear;
          result = (*fnptr)(2000);	// 与调用leapyear(2000)完全等价
      }
       
      int leapyear( int year){
          if(((year % 4 == 0) && (year % 100 != 0)) || (year % 400) == 0)
          	return ( 1);
          else
          	return ( 0);
      }

  • 作用

    • 函数派遣表

      指向函数的指针（函数指针）通常用于设计所谓函数派遣表（dispatch）,即通过下标数字来访问某个函数，这常见于菜单系统的设计中。如，index变量为0~9，当index为0时，调用函数fn0；为1时调用函数fn1…，则可设计如下：

      int fn0( ), fn1( ), fn2( ), … fn9( );

      int (*dispatch[ ])( ) = {fn0, fn1, fn2, … fn9};

      调用形式为：

      (*dispatch[index])( );

      • 例如：

        1
        2
        int New(), Open(), Save()…;
        int (*menu[ ])( ) = {New, Open, Save, … Close };

    • 作为函数参数：函数作为参数传递，可扩展一个函数的功能。

2.3.3 指针与数组

  1. 数组名是常量，指针是变量，即可以写pa = a，但不能写a = pa; a++等，即数组一经定义，其首地址将不允许改变。

  2. 字符串常量、字符串数组、字符串指针

    1. 对于字符串常量，可以把它看成一个无名字符数组，C编译程序会自动为它分配一个空间来存放这个常量，字符串常量的值是指向这个无名数组的第一个字符的指针，其类型是字符指针。所以，printf("a constant character string\n");传递给函数的是字符串第一个字符的指针。

    2. 1
      2
      3
      char a[]="hello", *p="hello";
      a[0] = ‘b’;   	/*正确 */
      *p = ‘b’;  /*错误，不能修改常量值*/

    3. 1
      2
      3
      4
      5
      char  *char_ptr, word[20];
      char_ptr = "point to me";		
      // 正确，把字符串常量第一个字符指针赋给指针变量。
      word = "you can't do this";	
      // 错误，正确做法为:strcpy(word, "…");

  3. 在函数定义中形参形式char s[ ]和char *s完全等价，即指向某类型的指针与该类型没有指明长度的数组是同一回事。用哪个取决于在函数里表达式的写法。

  4. 两种方式拷贝指针

    1. 通过指针赋值，如:px = py;两指针指向同一对象。该拷贝的最大负作用是当其中的一个指针被释放，另一个指针将成为无所指对象（指针悬挂）。(Shallow copy-浅拷贝)

      通过strcpy函数，如：strcpy(px, py);这种拷贝使得两个指针所指内容相同，但存放在各自的空间中。(Deep copy-深拷贝)

  5. 数组与指针

    1. 数组可以按指针方式使用，如：

      1
      2
      3
      int a[10],*p; 
      for(i=0; i<n; i++) 
          …*(a+i)…;

    2. 指针亦可按数组形式访问，如：

      1
      2
      void fun(int p[]){ 
      	…p[i]…

2.3.4 指针数组

  1. 指针数组与二维数组的区别

    1. 二者存储形式不同，但初始化形式与使用方式上是相通的，如：无论是指针数组，还是二维数组，下面两种形式访问的都是同一个元素，结果都是字符串”Friday”中的字符’y’：(days[5]+5) = days[5][5] = ‘y’；无论是二维数组还是指针数组，days[5]访问的都是字符串(即指向字符串的指针)”Friday

    2. 使用指针数组来存放不同长度的字符串可以节省存贮空间

    3. 二维数组

      1
      2
      3
      4
      5
      6
      7
      8
      9
      // 定义
      char days[7][10] = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};

      // 使用方式
      scanf("%s", days[i]);
      gets(days[i]);
      if(strcmp(days[i], "Friday")==0){}

      // 存储形式

    4. 指针数组

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      // 定义
      char *days[7] = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};

      // 使用方式
      char buf[32],*days[7];
      scanf("%s", buf);
      days[i] = (char *)malloc(strlen(buf)+1);
      strcpy(days[i], buf);
      if(strcmp(days[i], buf)==0)

      // 存储形式

2.4 malloc和free

  1. 函数原型：void *malloc(size_t size);

  2. 使用malloc初始化指针变量的常见用法

    1
    2
    3
    4
    5
    char *s; 
    int *intptr;
    s = (char *)malloc(32); /* s指向大小为32个字节（字符）的空间*/
    s = (char *)malloc(strlen(p)+1);/* s指向能正好存放字符串p的空间*/
    intptr = (int *)malloc(sizeof(int)*10);/* ptr指向能存放10个整型元素的空间*/

  3. 使用malloc申请到的动态空间在不用时应使用函数free释放，如free(s);

  4. 使用malloc和free函数要用#include <stdio.h>

2.5 简单文件操作

  1. 打开文件

    1
    2
    3
    4
    5
    6
    7
    8
    FILE *in, *out;
    // 为读写文件定义文件指针
    in = fopen("input.txt", "r");
    // 为输入打开一个给定文件"input.txt"；打开方式"r"为以只读方式打开一个文件
    out = fopen("output.txt", "w");
    // 为输出打开一个给定文件"output.txt"；打开方式"w"为以只写方式打开一个文件

    // 文件input.txt和output.txt位于与该执行程序.exe文件同一目录下（在vs code中则与工程在同一目录下）

  2. 读写文件

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    c = fgetc(in);
    // 从文件(input.txt)中读入一个字符
    fputc(c, out);
    // 输出一个字符到文件(output.txt)中
    fgets(s, n, in);
    // 从文件in中读入一行（最多读入n-1个字符），放入s字符数组中。返回s或NULL
    // 会在s最后加换行字符
    fputs(s, out);
    // 把字符串s（不一定含\n）写入文件out中，返回非负数或EOF
    // 不在输出后加换行字符
    fscanf(in, "%d", &score);
    // 从文件in中读入一个整数
    fprintf(out, "%d\n", score);
    // 输出一个整数到文件out中

  3. 关闭文件

    1
    2
    3
    4
    fclose(in);
    // 关闭文件input.txt
    fclose(out);
    // 关闭文件output.txt

  4. 示例：将一个文件内容拷贝到另一个文件

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    #include <stdio.h>
    int main(){
        int c;
        FILE *in, *out;
        
        in = fopen("input.txt", "r");
        out = fopen("output.txt", "w");
        while((c = fgetc(in)) != EOF){
            fputc(c, out);
        }
        
        fclose(in);
        fclose(out);
        return 0;
    }

2.6 define宏定义

  1. 定义常量，如：#define PI 3.14159
  2. 定义宏函数，#define 标识符(参数1, 参数2,...)，如：#define max(A,B) ((A)>(B)?(A):(B))
    • 宏定义名与参数间不能有空格，如：max(A,B)
    • 参数应该用括号括起来，如：(A)>(B)?(A):(B)

2.7 typedef类型定义

  • 语法格式：typedef 原类型名 新类型名，如：typedef int LENGTH;；其变量说明为LENGTH len, maxlen;，这与int len, maxlen;等价

  • 常见用法

    • 一些安全关键的软件中需要在程序中明确运行环境的数据类型长度，如：

      1
      2
      3
      typedef int INT32;
      typedef short INT16
      INT32 port0,port1;

    • 用来定义结构类型，如FILE就是一个用typedef定义的结构类型。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      struct _iobuf {
          char *_ptr;
          int _cnt;
          char *_base;
          int _flag;
          int _file;
          int _charbuf;
          int _bufsiz;
          char *_tmpfname;
      };
      typedef struct _iobuf FILE;

    • 数据结构中用来定义一个链表结点类型：

      1
      2
      3
      4
      5
      typedef struct node {
          int n;
          struct node *next;
      } *Nodeptr;
      Nodeptr list, p;		//struct node list, p;

  • 必须强调，typedef说明均不产生新的数据类型，也不定义存储单元，它只是给已有的类型又增添了新的类型名，没有产生新的语义，即用这种方法所说明的变量与明确指出说明的那些变量有相同的性质。

2.8 内存操作函数

  1. memcpy()

    • 函数原型：void *memcpy (void *dest, const void *src, size_t num);

    • 参数说明：

      • 函数memcpy从src位置开始向后复制num个字节的数据到dest的内存位置。
      • void *dest代表目标的内存地址，const void *src代表源内存地址。size_t即unsigned int类型。注意：num代表的是要拷贝的字节数，而非元素个数。
      • 该函数的返回值类型也为void *，也即只返回目标地址的数值。
      • 该函数用于实现没有重叠部分内存的内存数据拷贝。如果source和destination有任何的重叠，复制的结果都是未定义的。

    • 使用示例

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      int main(){
      	int arr1[] = { 1,2,3,4,5,6,7,8,9,10 };
      	int arr2[10] = { 0 };
      	memcpy(arr2, arr1, 20);    //拷贝20个字节，即5个int元素
       
      	float arr3[] = { 1.0f,2.0f,3.0f,4.0f };
      	float arr4[5] = { 0.0 };
      	memcpy(arr3, arr4, 8);    //拷贝8个字节，即2个float元素
       
      	return 0;
      }
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      //示例来自cplusplus官网

      #include <stdio.h>
      #include <string.h>
       
      struct {
          char name[40];
          int age;
      } person, person_copy;
       
      int main (){
      	char myname[] = "Pierre de Fermat";    //定义一个字符串
       
          /* 用 memcpy 拷贝字符串 */
          //每个char类型占一个字节，因此要拷贝的字节数即strlen()+1，加一是因为要把'\0'也拷贝过去。
      	memcpy ( person.name, myname, strlen(myname)+1 );
      	person.age = 46;
       
      	/* 用 memcpy 拷贝结构体 */
      	//sizeof操作符，可以直接得到结构体变量在内存中所占的字节数。
      	memcpy ( &person_copy, &person, sizeof(person) );
        
          //直接完成了结构体之间的数据拷贝：从person拷贝到person_cpy，不用手动转义，非常方便
          printf ("person_copy: %s, %d \n", person_copy.name, person_copy.age );

          return 0;
      }

  2. memmove()

    • 函数原型：void *memmove(void *dest, const void *src, size_t num );

    • 参数说明

      • 该函数的参数与返回值类型与memcpy()函数相同。该函数同样用作从src位置开始向后复制num个字节数据到dest的内存位置。
      • memmove()函数与memcpy()函数主要的区别在于memmove()可以进行有内存重叠的数据拷贝，而memcpy()绝对不能。

    • 使用示例

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      //示例来自cplusplus官网
       
      /* memmove example */
      #include <stdio.h>
      #include <string.h>
      int main (){
          char str[] = "memmove can be very useful......";
          memmove (str+20,str+15,11);
          //表示将包括str+15向后11个字节的内容移动到str+20位置
          puts (str);
          return 0; 
      }

  3. memset()

    • 函数原型：void *memset(void *ptr, int value, size_t num );

    • 参数说明

      • 第一个参数ptr为指针类型，表示要进行操作的内存的地址。如要对数组arr进行内存内容设置，则该参数的值为arr。
      • 第二个参数value为要设定的内存的值。该值的数据类型是int型，但char值也是可以的。
      • 第三个参数num为要设置值的内存的字节数。注意：是字节数，而不是元素的个数。如要改变两个int类型的值，num应为8 ，而不是2。

    • 使用示例

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      //示例来自cplusplus官网

      /* memset example */
      #include <stdio.h>
      #include <string.h>

      int main (){
          char str[] = "almost every programmer should know memset!";
          memset (str,'-',6);
          //表示将从str开始，包括str向后6个字节的内存内容置为'-'
          puts (str);
          return 0;
      }

      //输出：------ every programmer should know memset!

  4. memcmp()

    • 函数原型：int memcmp(const void *ptr1, const void *ptr2, size_t num );

    • 参数说明

      • 比较ptr1和ptr2指针开始的num个字节。
      • ptr1和ptr2分别是两个代表要比较的内存空间（一般是数组）的指针。
      • num是要比较的字节数。（注意：不是元素个数）。
      • 返回值为整型，若返回值>0，则ptr1的内存长度大于ptr2；若返回值==0，则二者相等；若返回值<0，则ptr1的内存长度小于ptr2

    • 使用示例

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      //示例来自cplusplus官网
       
      /* memcmp example */
      #include <stdio.h>
      #include <string.h>
       
      int main (){
          //创建两个要用作比较的数组
          char buffer1[] = "DWgaOtP12df0";    
          char buffer2[] = "DWGAOTP12DF0";

          //接受比较的结果
          int n;

          //要比较的字节数为buffer1的长度
          //两字符串的比较可以用strcmp(buffer1,buffer2)函数实现，原理大致相同。
          n = memcmp ( buffer1, buffer2, sizeof(buffer1) );

          if (n>0){
              printf ("'%s' is greater than '%s'.\n",buffer1,buffer2);
          }else if(n<0){
              printf ("'%s' is less than '%s'.\n",buffer1,buffer2);
          }else{
              printf ("'%s' is the same as '%s'.\n",buffer1,buffer2);
      	}
        return 0;
      }

2.9 命令行参数

  1. 在c语言中，主函数main还可以带有参数。形式如下：int main(int argc, char * argv[])或int main(int argc, char **argv)。其中argc为包含命令本身在内的参数个数，argv为指针数组，数组元素为指向各参数（包括命令本身）的指针。

  1. 执行程序的方式
    1. 法1：打开程序所在目录，把chengxuming.exe改为chengxuming，右键空白区域，在终端打开，输入chengxuming <参数1> <参数2>。
    2. 法2：cwenjianming.c，右键空白区域，在终端打开，输入gcc cwenjianming.c -o chengxuming，就会在相同目录下生成.exe文件，然后输入.\chengxuming.exe <参数1> <参数2>

2.10 struct结构体

  • 说明形式：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    struct 结构类型名{
        成员类型 成员名;
        成员类型 成员名;
        ...
    }

    // 例：
    struct date {
        int day;
        int month;
        int year;
        int yearday;
        char mon_name[4];
    };

    // 结构说明只是定义了一个结构的模版（template）或称为结构的框架，而并未定义结构的对象，也不为它分配存储空间。有了这样的结构模板说明后，一个结构变量可定义为：
    struct date d1, d2;
    // 定义时关键字struct和结构名date都不可少，可以把struct date一起看作是某种类型说明符（结构类型）

  • 结构变量的说明方式

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    // 1 无结构名
    struct {
      …
    } s1, s2;
    // 一般适用于说明本地变量。

    // 2 有结构名
    struct date {
      …
    } ;
    struct date s1, s2;
    //通常用来说明外部结构变量，或需要在多个函数中用到的相同的结构的变量。

    // 3 使用typedef
    typedef struct {
      …
    } DATE;
    DATE s1, s2, *pd, ad[10];
    // 使用typedef定义结构类型名后，结构变量的定义（或说明）就更简洁了。

  • 结构嵌套：结构成员可以是其他的结构类型，也可以是指向本身结构的指针，但不能是该结构本身，因为它无法确定此结构的边界，如：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    struct keyword{
        char *name;
        int count;
        struct keyword next;		// 错误！！！！！！
    } *base;

    struct keyword{
    char *name;
    int count;
    struct keyword *next;		//正确！！！！！！！！！！！！！
    } *base;

  • 初始化

    • 结构变量在定义时可以初始化，如：struct date d = {27, 12, 1984, 361, "Dec"};
    • 结构变量亦可通过整体赋值来初始化，如：struct date d1,d2 = {27, 12, 1984, 361, "Dec"};d1 = d2;

  • 结构成员的引用

    • 结构变量名.成员名

      1
      2
      3
      struct person emp;
      emp.birthday.year = 1970;
      emp.salary = 5000;

    • 指向结构变量的指针->成员名

      1
      2
      3
      4
      struct date *pd, d;		// pd是指向struct date的指针
      pd = &d;				// 指向一个已有结构变量
      //或 pd = (struct date *) malloc(sizeof(struct date));
      pd->year = 1958;		// 与 (*pd).year = 1958 等价

2.11 自引用结构

2.11.1 （动态）数据的组织与存储方式

  • 顺序组织，如数组
    • 需要连续空间
    • 数据项的插入或删除操作需要移动大量数据
  • 非顺序（动态）组织，如链表，二叉树等
    • 不需要连续空间
    • 数据项的插入或删除操作非常简单

2.11.2 自引用结构成员

分为两部分：各种实际数据成员+一个或几个指向自身结构的指针

1
2
3
4
5
// 通常结构
struct Type {
    data_member;	// 如 int n;
    struct Type *link;
};

1
2
3
4
5
6
// 链表结构
struct  word {
    char *name;
    int count;
    struct word *next;
} *base;

1
2
3
4
5
6
7
// 二叉树结构
struct tnode {
    char *word;
    int count;
    struct tnode *left;
    struct tnode *right;
} *root;

2.11.3 注意事项

  1. 应用：动态数组结构，如链表、树等特别适用于数组项数不确定的数据的组织。

  2. 使用时应有一个头指针（first,head,root），并使用malloc为每个节点分配空间,如：first = p = (struct node *)malloc(sizeof(struct node));

  3. 使用时，通常使用如下方式将节点链接起来：

    p->next = (struct node *)malloc(sizeof(struct node));

    p = p->next;

  4. 使用时要注意(头)节点丢失问题，不要轻易移动头节点位置。

2.12 链表的生成

2.12.1 链表结构

1
2
3
4
struct link {
    int n;
    struct link *next;
};

2.12.2 创建链表

1
2
3
4
5
6
7
8
9
10
11
12
struct link *first=NULL, *p,*q;
for(i=0; i< 10; i++){
    q = (struct link *)malloc(sizeof(struct link));		// 创建一个新的节点（本节点）
    q->n = i; 
    q->next = NULL;
    if(first == NULL){		// 第一个节点
        first = p = q;
    }else{
        p->next = q;	// 使前一个节点指向本节点（当前的最后一个节点）
        p = p->next;	// 指针p继续移动，指向当前的最后一个节点
    }
}

2.12.3 插入和删除节点

1
2
3
4
5
6
7
// 1 在p后插入q
q->next = p->next;
p->next = q;
// 2 删除p的下一节点
q = p->next;
p->next = p->next->next;
free(q);

2.13 union联合

  • 定义形式：union 联合名 {分量表} 联合变量名；

  • 用途：在一个位置存储多个不会同时用到的数据，用于节省内存

  • 形象的理解（来自文心一言）：想象一下，你有一个房间，这个房间可以当作书房使用，也可以当作卧室使用，但不能同时是书房和卧室。union就类似于这个房间，你可以在其中存放书（一种数据类型），也可以在其中放床（另一种数据类型），但你不能同时放书和床。

  • 示例：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    union Data {  
        int i;  
        float f;  
        char str[20];  
    };  
      
    int main() {  
        union Data data;  
      
        data.i = 10; // 此时，union中存储的是一个整数  
        printf("%d\n", data.i); // 输出：10  
      
        data.f = 220.5; // 现在，union中存储的是一个浮点数，之前存储的整数被覆盖了  
        printf("%f\n", data.f); // 输出：220.500000  
      
        strcpy(data.str, "Hello"); // 现在，union中存储的是一个字符串，之前存储的浮点数被覆盖了  
        printf("%s\n", data.str); // 输出：Hello  
      
        return 0;  
    }

  • 注意

    • union中的所有成员都共享同一块内存空间。也就是说，无论union中有多少个成员，它总是只占用最大的那个成员所需的内存空间。当你给union的一个成员赋值时，其他成员的值就会被覆盖，因为它们都是指向同一块内存的。
    • union不提供类型安全性，所以使用时要特别小心，确保你知道当前union中存储的是什么类型的数据。

2.14 其他

  • #include <stdlib.h>里面有int atoi(char s[]);，可以把字符串转化为相应整数。

例题

例1 简单文件操作、宏定义

1 问题提出

问题
  • 问题描述：从文件中查找包含给定字符串的行。
  • 输入形式：从标准输入中分两行分别输入被查找的文件及要查找的字符串（中间不含空格）。
  • 输出形式：在屏幕上输出文件中包含给定字符串的行。
  • 样例输入： 
    在键盘输入如下文件名及字符串:
test.txt
the
文件 test.txt 内容如下：
Now is the time
for all good
men to come to the aid
of their party
  • 样例输出： 
    屏幕输出为
this is the time
men to come to the aid
of their party
问题分析
  • 数据结构设计：分析问题描述，显然需要三个字符数组变量，分别存放文件名、要查找的字符串及从文件中读入的行。
    char filename[32], str[81], line[1024];
    （一个文件名长度通常不超过32个字符；屏幕上一行通常显示80个字符；而1024是一般文件的最大物理行长度。当然这些取决于具体系统实现。）
  • 数据输入
    用scanf("%s", )读入文件名和要查找的串
    从文件中读入一行用fgets()，不用fscanf()是因为fscanf遇空行停止
  • 数据处理
    从所读入的一行中查找给定的字符串（即从一个字符串中查找另一个字符串）。可用一个单独的函数index实现在一个字符串中查找另一个字符串。

2 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
#define MAXLINE  1024
int index(char s[ ], char t[ ]);	// 找子串

int main( ){
	char filename[64], s[81], line[MAXLINE];
	FILE *fp;
	scanf("%s", filename);
	scanf("%s", s);
    // 由于打开一个文件的操作可能失败，因此需要判断fopen的返回值，进行错误处理
	if((fp = fopen(filename, "r")) == NULL){
		printf("Can't open file %s!\n", filename);
		return 1;
	}
    
	while(fgets(line, MAXLINE-1, fp) != NULL)
		if(index(line, s) >= 0)
        	printf("%s", line);
       return 0;
}

int index(char s[ ], char t[ ]){
	int i, j, k;
	for(i =0; s[i] != ‘\0’; i++){
		for(j=i,k=0;t[k]!=‘\0’&&s[j]==t[k]; j++,k++)
			;
        if(t[k] == ‘\0’){	//找到了
            return (i);
        }
	}
	return (-1);
}

3 拓展

  1. 字符串查找函数时间复杂度为O(n*m)，n为源串的长度，m为要查找的串的长度

    1. KMP算法

    2. 另一种字符串查找算法（只需一层循环）

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      int index(char s[], char t[])
      {
          int i=0, j=0;	 //设置查找的起始位置
          while(s[i] != ‘\0’ && t[j] != ‘\0’) {
              if(s[i] == t[j]){	//若字符相等，继续查找下一个字符
                  i++; j++;
              }else{	//若字符不等，则s中退回到上次查找开始的下一个位置
                  i = i-j+1;
                  j = 0;
              }
          }
          if(t[j] == ‘\0’){	//查找到字符串t，返回t在s中的起始位置
              return i-j;
          }else{
              return -1;
          }
      }

  2. 区分了大小写：

    使用tolower()函数实现大小写无关的字符串查找（头文件或者宏定义或者单独写一个函数）

  3. 其他功能的实现

    1. 如何查找子字符串的最后一次出现？
    2. 如何查找一个字符串在一个文件中的所有出现？（如office软件中的查找功能）
    3. 如何查找给定串并用另一个替换串？（如office软件中的替换功能）
    4. 如何实现模糊查找？（如UNIX命令grep）

例2 二维、多维数组

1 问题提出

问题 
  • 用一个二维方阵（最小为3X3，最大为50X50）表示一片海域。方阵中的元素只由0和1组成。1表示海岸线。计算由海岸线围起来的小岛面积（即：由1围起来的区域中0的个数）。如下图所示8X8方阵表示的小岛面积为9：
0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 1 0 1 0 0
0 0 1 0 0 0 1 0
0 1 0 0 0 1 0 0
0 1 0 1 0 1 0 0
0 1 1 0 1 0 0 0
0 0 0 0 0 0 0 0
上述方阵表示的海域满足下面两个要求：
    1、小岛只有一个。
    2、用1表示的海岸线是封闭的，但有可能是凸的，也有可能是凹的。
  • 输入形式：先从标准输入中输入方阵的阶数，然后从下一行开始输入方阵的元素（只会0或1）。
  • 输出形式：在标准输出上输出用整数表示的小岛面积。。
  • 样例输入： 
    8
0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 1 0 1 0 0
0 0 1 0 0 0 1 0
0 1 0 0 0 1 0 0
0 1 0 1 0 1 0 0
0 1 1 0 1 0 0 0
0 0 0 0 0 0 0 0
  • 样例输出：9

2 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<stdio.h>
int main(){
    int a[50][50]={0}, i, j, k, c, n, area=0;
    // 读入
    scanf("%d",&n);
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            scanf("%d",&a[i][j]);
        }
    }
    
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            c=0;
            if(a[i][j]==0){
                for(k=i;k<n;k++){	//下面有1
                    if(a[k][j]==1) {
                        c++; break;
                    }
                }
                for(k=i;k>=0;k--){	//上面有1
                    if(a[k][j]==1) {
                        c++; break;
                    }
                }
                for(k=j;k<n;k++){	//右面有1
                    if(a[i][k]==1) {
                        c++; break;
                    }
                }
                for(k=j;k>=0;k--){	//左面有1
                    if(a[i][k]==1){
                        c++; break;
                    }
                }
            }
            if(c==4){	//如果上下左右都有1，这个0就被包了起来
                area++;
            }
        }
    }
    printf("%d",area);
    return 0;
}

例3

1 问题

输出输入行中的最长行。

2 代码实现

  • 法1：数组方式实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdio.h>
#define MAXLINE	1024

int str_len(char s[ ]);
void str_copy(char s[ ], char t[ ]);

int main( ){	/* find longest line */
    int len;	// current line length
    int max;		// maximum length seen so far
    char line[MAXLINE];	// current input line
    char save[MAXLINE];	// longest line saved
    max = 0;
    while( gets(line)  != NULL ){
		len = str_len(line);
    	if( len > max ) {
    		max = len;
    		str_copy(save, line);
    	}
    }
    if( max > 0)
    	printf("%s", save);
	return 0;
}

int str_len(char s[ ]){
    int i = 0;
    while(s[i] != ‘\0’)
        i++;
    return i;
}

void str_copy(char s[ ], char t[ ]){
    int i = 0;
    while((s[i] =t[i] )!= ‘\0’)
        i++;
 }
  • 法2：指针方式实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
#define MAXLINE	1024
int str_len(char s[]);
int main( ){ 	// find longest line
	int len, max;	
    // current length and maximum length seen so far
	char *curptr, *saveptr,*tmp;
    //current  line pointer and longest line pointer saved
    char  save1[MAXLINE], save2[MAXLINE];
    curptr = &save1[0];
    saveptr= &save2[0];  
    max = 0;
    while( gets(curptr)  != NULL ){
        len = str_len(curptr);
        if( len > max ) {
            max = len;
            tmp = curptr;
            curptr = saveptr;
            saveptr = tmp; 
        }
    }
    if( max > 0)
    	printf("%s", saveptr);
    return 0;
}

例4 命令行参数

1 问题

实现一个命令echo，其将命令后的正文串显示在屏幕上，如：C> echo hello world屏幕输出：hello world

2 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 法1
int main( int argc, char *argv[ ]){
   for(int i=1; i<argc; i++){
        printf("%s ", argv[i]);
    }
    return 0;
}

// 法2
int main(int argc, char *argv[ ]){
    while(--argc > 0)
        printf("%s ", *++argv);
    return 0;
}

例5 结构体

1 问题

实现复数运算

2 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
struct complex{
    float  real;
    float  imag;
};
struct complex addComplex(struct complex c1, struct complex c2);

int main(){
    struct complex c1, c2, c3;
    scanf("%f %f %f %f", &c1.real, &c1.imag, &c2.real, &c2.imag);
    c3 = addComplex(c1, c2);
    printf("(%.2f, %.2f) + (%.2f, %.2f) = (%.2f, %.2f)\n", c1.real, c1.imag, c2.real, c2.imag, c3.real, c3.imag);
    return 0;
}

struct complex addComplex(struct complex c1, struct complex c2){
    struct complex tmp;
    tmp.real = c1.real + c2.real;
    tmp.imag = c1.imag + c2.imag;
    return tmp;
}

例6 结构体

1 问题

编写一个程序，统计输入中C语言每个关键字的出现次数。

2 算法设计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 1 定义一个结构说明泳衣表示关键字与其出现次数
struct Key {
    char *keyword;
    int count;
};
// 2 关键字表的组织：使用一个有序的结构数组来存放关键字表及关键字出现次数：
struct Key Keytab[ ] = {
    "auto", 0,
    "break",0,
    "case", 0,
    …
    "while", 0
};
// 3 主要算法
While (仍有新单词读入)
    If(在关键字表中查找并找到输入的单词)
        相应关键字次数加1；
输出关键字及出现次数；
	// 3.1 读入新单词
        // 设函数
    		char getWord(char word[],int lim)；
        // 从标准输入中读入一个长度不超过lim-1的单词，并返回单词类型。
		// 为何不用scanf的%s来读?如：while(scanf(‘%s”, word) > 0)…
	// 3.2 查找输入的单词
    	// 设函数
			struct Key *binary(char *word, struct Key tab[ ], int n)
		// 在关键字表tab中查找单词word是否存在。如果找到，则返回其出现位置。n为关键字表的长度（关键字个数）。
    // 3.3 输出关键词及出现次数
        // 设函数
			void printKey(struct Key tab[ ], int n) 
		// 输出关键字及出现次数。
// 4 二分查找

3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <stdio.h>
struct Key {
    char *keyword;
    int keycount;
} Keytab[ ] = {
    "auto", 0,
    "break", 0,
    "case", 0,
    …
    "while", 0
};

#define MAXWORD 20
#define NKEYS (sizeof(Keytab) / sizeof(struct Key))
#define LETTER ‘a’
#define DIGIT ‘0’
struct Key *binary(char *word, struct Key tab[ ], int n);
char getword(char *w, int lim);
char type( int c);
void printKey(struct Key tab[ ], int n);

int main( ){	// count  C keyword
    int t;
    char word[MAXWORD];
    struct Key *p;

    while((t = getword(word, MAXWORD)) != EOF)
        if(t == LETTER)		//如果读到词汇返回LETTER
            if((p = binary(word, Keytab, NKEYS)) != NULL)
            	p->keycount++;
    printKey(keytab, NKEYS);
    return 0;
}

struct Key *binary(char *word, struct Key tab[ ], int n){
    int cond;
    struct Key *low = &tab[0];
    struct Key *high = &tab[n-1];
    struct Key *mid;

    while(low <= high){
        mid = low + (high – low) / 2;
        if((cond = strcmp(word, mid->keyword)) < 0)
        	high = mid – 1;
        else if ( cond > 0)
        	low = mid + 1;
        else
        	return (mid);
    }
    return (NULL);
}

char getword(char *w, int lim){
    int c, t;

    if(type(c = *w++ = getchar( )) != LETTER){
        *w = ‘\0’;
        return (c);
    }
    while(--lim > 0) {
        t = type(c = *w++ = getchar( ));
        if( t != LETTER && t != DIGIT){
            ungetc(c);
            break;
        }
    }
    *(w-1) = ‘\0’;
    return (LETTER);
}
/* 从文件中识别出标识符
int getword(char s[], FILE *fp){
    int c,  i = 0;
    while(type(c=fgetc(fp))!= LETTER)  
        if(c == EOF) return c;  
        else continue;
    s[i++] = c;
    while((c=fgetc(fp))!=EOF){
         if(type(c)!=LETTER&&type(c)!=DIGTH)
              break; 
         s[i++] = c;
    }
    s[i]='\0';
    return 1;
} */

char type(int c){	// return type of ASCII character
    if( c >= ‘a’ && c <= ‘z’ || c >= ‘A’ && c <= ‘Z’)
    	return ( LETTER );
    else if ( c >= ‘0’ && c <= ‘9’)
    	return ( DIGIT );
    else
        return (c);
}

void printKey(struct Key tab[ ], int n){
    struct Key *p;
        for(p=tab, p < tab+n; p++)
            if(p->keycount > 0)
            	printf("%4d%s\n", p->keycount, p->keyword);
}

例7 结构体、二分查找

1 问题

  • 问题描述

    从文件sorelist.txt中读入最多不超过50个学生的学生信息（包括空格隔开的学号、姓名、成绩信息，以学号从低到高排序），分别按姓名和成绩排序输出学生信息到文件sorelist_sort.txt中。

  • 输入形式

    从文件scorelist.txt中读入最多不超过50个学生的学生信息： 第一行为学生人数； 后面每一行为空格隔开的学生学号、姓名、成绩，其中学号和成绩为整数，姓名为字符串，不超过5位英文字符。

  • 输出形式

    以姓名顺序（按字典顺序）及成绩顺序（从高到低）将学生信息分别输出到文件scorelist_sort.txt中，中间用一空行分隔。每行输出一位学生的信息，其中学号占3位，姓名（英文）占6位，成绩占5位。

  • 输入样例

    文件scorelist.txt中内容为：

    1
    2
    3
    4
    1 Li  86
    2 Zhao 90
    3 Wang 87
    4 Zhang 56

  • 输出样例

    程序运行后，文件scorelist_sort.txt中内容为：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    1 Li 86
    3 Wang 87
    4 Zhang 56
    2 Zhao 90

    2 Zhao 90
    3 Wang 87
    1 Li 86
    4 Zhang 56

2 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <stdio.h>
#include <string.h>

struct Student {
	int no;
	char name[6];
	int score;
};

void sortbyName(struct Student array[], int n);
void sortbyScore(struct Student array[], int n);
void print(FILE *fp, struct Student array[], int n);

int main(){
    FILE *in, *out;
    struct Student info[51];
    int i,n;
    // 输入文件打开失败
    if((in=fopen("scorelist.txt","r")) == NULL){
        printf("Cann't Open file scorelist.txt!\n");
        return 1;
    }
    // 输出文件打开失败
    if((out=fopen("scorelist_sort.txt","w")) == NULL){
        printf("Cann't Open file scorelist_sort.txt!\n");
        return 1;
    }
    // 读入
    fscanf(in,"%d",&n);
    for(i=0;i<n;i++)
        fscanf(in, "%d%s%d", &info[i].no, info[i].name, &info[i].score);
    // 姓名顺序输出
    sortbyName(info, n);
    print(out, info, n);
    // 成绩顺序输出
    sortbyScore(info, n);
    print(out,info, n);
    // 关闭文件
    fclose(in);
    fclose(out);
    return 0;
}

void sortbyName(struct Student array[], int n){		// 姓名顺序
    int i, j;
    struct Student tmp;
    for(i=0; i<n; i++){
        for(j=i; j<n; j++){
            if(strcmp(array[i].name,array[j].name)>0){
                tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
            }
        }
    }
}

void sortbyScore(struct Student array[], int n){	// 成绩顺序
    int i, j;
    struct Student tmp;
    for(i=0; i<n; i++){
        for(j=i; j<n; j++){
            if(array[i].score < array[j].score){
                tmp = array[i];
				array[i] = array[j];
                array[j] = tmp;
            }
        }
    }
}

void print(FILE *fp, struct Student array[], int n){	// 输出
    int i;
    for(i=0;i<n;i++)
        fprintf(fp, "%3d%6s%5d\n", array[i].no, array[i].name, array[i].score);
	fprintf(fp, "\n");
}

例8 链表

1 问题

  • 命令tail用来显示一个文件的最后n行，其格式为：tail [-n] filename。其中：n表示需要显示的行数，省略时n的值为10；filename为给定文件名。如，命令tail –20 example.txt表示显示文件example.txt的最后20行。
  • 实现该程序，该程序应具有一定的错误处理能力，如能处理非法命令参数和非法文件名。

2 问题分析

  • 如何得到需要显示的行数和文件名？

    • 使用命令行参数：int main(int argc, char *argv[])
    • 行数n = atoi(argv[1]+1)
    • 文件名filename = argv[2]

  • 如何得到最后n行？

    • 方法1：使用n个节点的循环链表。链表中始终存放最近读入的n行。

      1. 首先创建一个空的循环链表；

      2. 然后再依次读入文件的每一行挂在链表上，最后链表上即为最后n行。

    • 方法2：使用一个n个元素的指针数组。

      依次读入每一行，然后循环挂到指针数组上。

      1
      2
      3
      4
      5
      6
      char *lineptr[N];	//存入所读入的行
      char line[LEN];		//当前读入行
      int i;				//读入的行数

      lineptr[i % n] = (char *)malloc(strlen(line)+1);
      strcpy(lineptr[i%n], line);

    • 方法3：两次扫描文件。

      • 第一遍扫描文件，用于统计文件的总行数N；

      • 第二遍扫描文件时，首先跳过前面N-n行，只读取最后n行。

        如何开始第二遍扫描？

        fseek(fp, 0, SEEK_SET);将文件读写位置移至文件头或（关闭后）再次打开同一个文件

    • 方法4：设计函数fbgetc(fp);，从文件尾开始，每次倒读一个字符；fbgets(buf,size,fp);从文件尾开始每次倒读一行

3 代码实现（循环链表）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define DEFLINES 10
#define MAXLEN 81
struct Node {
    char *line;
    struct Node *next;
};
int main(int argc, char *argv[ ]) {
    char curline[MAXLEN], *filename;
    int n = DEFLINES, i;		// 默认十行
    struct Node *first, *ptr;
    FILE *fp;
    // 读入行数、文件名
    if(argc == 3 && argv[1][0] == '-'){		// 指定打印行数
        n = atoi(argv[1] + 1);
        filename = argv[2];
    }else if(argc == 2){
        filename = argv[1];
    }else{
        printf("Usage: tail [-n] filename\n");
        return (1);
    }
    
    // 创建循环链表
    if((fp = fopen(filename, "r")) == NULL){
        printf(" Can't open file: %s !\n", filename);
        return (-1);
    }
    first = ptr = (struct Node *)malloc(sizeof ( struct Node));
    first->line = NULL;
    for(i=1; i<n; i++){
        ptr->next = (struct Node *)malloc(sizeof ( struct Node));
        ptr = ptr->next;
        ptr->line = NULL;
    }
    ptr->next = first;
    	// 将链表的最后一个节点指向头节点，以构成一个循环链表。
    ptr = first;
	
    // 读入文件中内容
    while(fgets(curline, MAXLEN, fp) != NULL){
        if(ptr->line != NULL)	//链表已经满了，需要释放掉不需要的行
        	free(ptr->line);
        ptr->line = (char *) malloc(strlen(curline)+1);
        strcpy(ptr->line, curline);
        ptr = ptr->next;
	}
    for(i=0; i<n; i++) {
        if(ptr->line != NULL)
        	printf("%s",ptr->line);
        ptr = ptr->next;
    }
    fclose(fp);
    return 0;
}
学习经验 > 数据结构
#学习经验
【数据结构】ds笔记1-数据结构基础
http://example.com/2024/03/09/LE-ds1/
Author
John Doe
Posted on
March 9, 2024
Licensed under